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]++;
	}
	vector<int> already_sorted;
	for(int i=k; i<=n; i++){
		int sum = sor[i] - sor[i-k+1];
		if(sum == k - 1){
			already_sorted.push_back(i);
		}
	}
	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++){
		disj.uni(already_sorted[0], already_sorted[i]);
	}
	for(int i=k; i<=n; i++){
		if(disj.find(i) == i) ret++;
	}
	cout << ret << endl;
}

Submission Info

Submission Time
Task B - Sorting a Segment
User koosaga
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1899 Byte
Status AC
Exec Time 55 ms
Memory 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