oj.uz

Submission #287352

# Submission time Handle Problem Language Result Execution time Memory
287352 2020-08-31T16:16:50 Z Namnamseo Teams (IOI15_teams) C++17
100 / 100
 3328 ms 98392 KB 
#include <cstdio>
#include <cstdlib>

#include <vector>
#include <stack>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;

typedef pair<int,int> pp;
stack<pp > st;
stack<int> left;
int n;

struct seg2d{
	static const int M=524288;
	vector<int> tree[M*2];
	void addPoint(int x,int y){
		y+=M;
		while(y){
			tree[y].pb(x);
			y>>=1;
		}
	}
	void init(){
		int i;
		for(i=1;i<2*M;++i) sort(all(tree[i]));
	}
	inline int get(int point,int x,int y){
		return max(0,int(upper_bound(all(tree[point]),y) -
						 lower_bound(all(tree[point]),x)));
	}
	int query(int l,int r,int x,int y){
		int ret=0;
		x+=M; y+=M;
		while(x<=y){
			if(x==y){
				ret += get(x,l,r); break;
			}
			if(x&1)      ret+=get(x++,l,r);
			if((y&1)==0) ret+=get(y--,l,r);
			x>>=1; y>>=1;
		}
		return ret;
	}
	int get_over(int x1,int x2,int k){
		int pos=1;
		int cnt=0;
		while(pos<M){
			int l=pos*2, r=l+1;
			int tmp=get(l,x1,x2);
			if(cnt+tmp < k){
				cnt += tmp;
				pos=r;
			} else pos=l;
		}
		return pos-M;
	}
} seg;
void init(int N, int A[], int B[]) {
	int i;
	n=N;
	for(i=0;i<N;++i) seg.addPoint(A[i],B[i]);
	seg.init();
}

int can(int M, int K[]) {
	sort(K,K+M);
	int i;
	while(st  .size()) st  .pop();
	while(left.size()) left.pop();
	st.push({0,n});
	left.push(0);
	for(i=0;i<M;++i){

		int& x=K[i];
		
		int curcnt=x, lasty=x-1;
		
		for(;st.size()>1;){
			auto t=st.top();
			if(t.second < x){
				st.pop(); left.pop();
				continue;
			}
			int cnt=seg.query(t.first+1, x, lasty+1, t.second) + left.top();
			if(curcnt <= cnt) {
				break;
			}
			st.pop(); left.pop();
			lasty  = t.second;
			curcnt -= cnt;
		}
		
		pp t=st.top();
		if(seg.query(t.first+1, x, lasty+1, t.second) + left.top() < curcnt) return 0;
		
		int R=min(t.second, seg.get_over(t.first+1, x, curcnt + seg.query(t.first+1, x, 0, lasty) ));
		
		left.push(seg.query(st.top().first+1,x,lasty+1,R)-curcnt);
		st.push({x,R});
	}
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24960 KB Output is correct
2 Correct 19 ms 24960 KB Output is correct
3 Correct 18 ms 24960 KB Output is correct
4 Correct 19 ms 24960 KB Output is correct
5 Correct 19 ms 24960 KB Output is correct
6 Correct 19 ms 24960 KB Output is correct
7 Correct 21 ms 24960 KB Output is correct
8 Correct 21 ms 24960 KB Output is correct
9 Correct 20 ms 24960 KB Output is correct
10 Correct 20 ms 24960 KB Output is correct
11 Correct 19 ms 24960 KB Output is correct
12 Correct 21 ms 24960 KB Output is correct
13 Correct 20 ms 24960 KB Output is correct
14 Correct 20 ms 24960 KB Output is correct
15 Correct 19 ms 24960 KB Output is correct
16 Correct 19 ms 24960 KB Output is correct
17 Correct 19 ms 24960 KB Output is correct
18 Correct 19 ms 24960 KB Output is correct
19 Correct 20 ms 24960 KB Output is correct
20 Correct 19 ms 24960 KB Output is correct
21 Correct 20 ms 24960 KB Output is correct
22 Correct 20 ms 24960 KB Output is correct
23 Correct 20 ms 24960 KB Output is correct
24 Correct 19 ms 24960 KB Output is correct
25 Correct 20 ms 24960 KB Output is correct
26 Correct 19 ms 24960 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 38236 KB Output is correct
2 Correct 220 ms 38364 KB Output is correct
3 Correct 223 ms 38252 KB Output is correct
4 Correct 221 ms 38620 KB Output is correct
5 Correct 123 ms 34872 KB Output is correct
6 Correct 121 ms 34740 KB Output is correct
7 Correct 119 ms 34736 KB Output is correct
8 Correct 125 ms 34736 KB Output is correct
9 Correct 79 ms 33880 KB Output is correct
10 Correct 70 ms 33764 KB Output is correct
11 Correct 64 ms 34012 KB Output is correct
12 Correct 77 ms 34292 KB Output is correct
13 Correct 156 ms 34660 KB Output is correct
14 Correct 134 ms 36488 KB Output is correct
15 Correct 197 ms 38116 KB Output is correct
16 Correct 199 ms 38244 KB Output is correct
17 Correct 85 ms 34892 KB Output is correct
18 Correct 90 ms 34900 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 38760 KB Output is correct
2 Correct 239 ms 38748 KB Output is correct
3 Correct 712 ms 41948 KB Output is correct
4 Correct 219 ms 38624 KB Output is correct
5 Correct 398 ms 35116 KB Output is correct
6 Correct 370 ms 35040 KB Output is correct
7 Correct 127 ms 34992 KB Output is correct
8 Correct 305 ms 34900 KB Output is correct
9 Correct 79 ms 34392 KB Output is correct
10 Correct 103 ms 34004 KB Output is correct
11 Correct 111 ms 34004 KB Output is correct
12 Correct 173 ms 33972 KB Output is correct
13 Correct 543 ms 34816 KB Output is correct
14 Correct 892 ms 40004 KB Output is correct
15 Correct 383 ms 38628 KB Output is correct
16 Correct 387 ms 38628 KB Output is correct
17 Correct 304 ms 35276 KB Output is correct
18 Correct 243 ms 35260 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 92560 KB Output is correct
2 Correct 1322 ms 92760 KB Output is correct
3 Correct 2827 ms 98392 KB Output is correct
4 Correct 1304 ms 92780 KB Output is correct
5 Correct 1522 ms 73180 KB Output is correct
6 Correct 1425 ms 72952 KB Output is correct
7 Correct 572 ms 73040 KB Output is correct
8 Correct 1241 ms 73180 KB Output is correct
9 Correct 347 ms 68704 KB Output is correct
10 Correct 342 ms 68896 KB Output is correct
11 Correct 391 ms 68864 KB Output is correct
12 Correct 576 ms 69012 KB Output is correct
13 Correct 2032 ms 71908 KB Output is correct
14 Correct 3328 ms 94328 KB Output is correct
15 Correct 1528 ms 89300 KB Output is correct
16 Correct 1514 ms 90200 KB Output is correct
17 Correct 869 ms 79016 KB Output is correct
18 Correct 842 ms 78116 KB Output is correct