Contest Duration: - (local time) (110 minutes) Back to Home

Submission #7643053

Source Code Expand

Copy
```#include<bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
const int MAXT = 530000;

struct disj{
int pa[MAXN];
void init(int n){
iota(pa, pa + n + 1, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;

struct seg{
int tree[MAXT], lim;
void init(int n, int *a){
memset(tree, 0x3f, sizeof(tree));
for(lim = 1; lim <= n; lim <<= 1);
for(int i=1; i<=n; i++){
tree[i + lim] = a[i];
}
for(int i=lim; i; i--){
tree[i] = min(tree[2*i], tree[2*i+1]);
}
}
int query(int s, int e){
s += lim;
e += lim;
int ret = 1e9;
while(s < e){
if(s%2 == 1) ret = min(ret, tree[s++]);
if(e%2 == 0) ret = min(ret, tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) ret = min(ret, tree[s]);
return ret;
}
}seg, ges;

int a[MAXN], b[MAXN];
int sor[MAXN];
int n, k;

int main(){
cin >> n >> k;
if(k == 1){
cout << 1 << endl;
return 0;
}
disj.init(n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
b[i] = -a[i];
}
seg.init(n, a);
ges.init(n, b);
for(int i=2; i<=n; i++){
sor[i] = sor[i-1];
if(a[i-1] < a[i]) sor[i]++;
}
for(int i=k; i<=n; i++){
int sum = sor[i] - sor[i-k+1];
if(sum == k - 1){
}
}
for(int i=k+1; i<=n; i++){
int minv = seg.query(i - k + 1, i - 1);
int maxv = -ges.query(i - k + 1, i - 1);
if(a[i-k] < minv && maxv < a[i]){
disj.uni(i-1, i);
}
}
int ret = 0;
for(int i=1; i<sz(already_sorted); i++){
}
for(int i=k; i<=n; i++){
if(disj.find(i) == i) ret++;
}
cout << ret << endl;
}
```

#### Submission Info

Submission Time 2019-09-21 22:38:23+0900 B - Sorting a Segment koosaga C++14 (GCC 5.4.1) 700 1899 Byte AC 55 ms 8696 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:64:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
 AC × 3
 AC × 32
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 4736 KB
01-02.txt AC 3 ms 4736 KB
01-03.txt AC 44 ms 7040 KB
01-04.txt AC 40 ms 7168 KB
01-05.txt AC 22 ms 6400 KB
01-06.txt AC 33 ms 7420 KB
01-07.txt AC 30 ms 8696 KB
01-08.txt AC 29 ms 7552 KB
01-09.txt AC 29 ms 8696 KB
01-10.txt AC 30 ms 7680 KB
01-11.txt AC 32 ms 7552 KB
01-12.txt AC 46 ms 7552 KB
01-13.txt AC 45 ms 7552 KB
01-14.txt AC 54 ms 7552 KB
01-15.txt AC 53 ms 7552 KB
01-16.txt AC 55 ms 7552 KB
01-17.txt AC 39 ms 7552 KB
01-18.txt AC 42 ms 7552 KB
01-19.txt AC 43 ms 7552 KB
01-20.txt AC 47 ms 8188 KB
01-21.txt AC 39 ms 7936 KB
01-22.txt AC 33 ms 7552 KB
01-23.txt AC 36 ms 7552 KB
01-24.txt AC 37 ms 7552 KB
01-25.txt AC 25 ms 7552 KB
01-26.txt AC 26 ms 7552 KB
01-27.txt AC 25 ms 7552 KB
01-28.txt AC 24 ms 7552 KB
01-29.txt AC 24 ms 7552 KB
sample-01.txt AC 3 ms 4736 KB
sample-02.txt AC 3 ms 4736 KB
sample-03.txt AC 3 ms 4736 KB