oj.uz

답안 #129997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129997 2019-07-13T18:30:49 Z Adhyyan1252 팀들 (IOI15_teams) C++11
100 / 100
 2985 ms 399032 KB 
#include "teams.h"
#include<bits/stdc++.h>

using namespace std;
#define DEBUG false
#define INF 1e7

int n; 
struct node{
	node *l, *r;
	int sum;

	node(int v = 0){
		l = r = NULL; sum = v;
	}

	node(node* L, node* R){
		l = L; r = R;
		sum = L->sum + R->sum;
	}

};

node* build(int s, int e){
	if(s == e){
		return new node(0);
	}
	int m = (s + e)/2;
	return new node(build(s, m), build(m+1, e));
}

node* upd(node* i, int s, int e, int indx, int val){
	if(s == e){
		return new node(val);
	}
	int m = (s + e)/2;
	if(indx <= m) return new node(upd(i->l, s, m, indx, val), i->r);
	else return new node(i->l, upd(i->r, m+1, e, indx, val));
}


int query(node* i, int s, int e, int l, int r){
	if(l <= s && e <= r) return i->sum;
	if(s > e || s > r || e < l) return 0;
	int m = (s + e)/2;
	return query(i->l, s, m, l, r) + query(i->r, m+1, e, l, r);
}

vector<int> t, lazy;

vector<node*> roots;

void prop(int i, int s, int e){
	if(lazy[i] == -1) return;
	if(s != e){
		lazy[i*2] =  lazy[i];
		lazy[i*2+1] = lazy[i];
	}
	if(lazy[i] == INF) t[i] = 0;
	else t[i] = query(roots[lazy[i]], 0, n-1, s, e);
	lazy[i] = -1;
}

int pro(int i, int s, int e, int indx, int rem, int k, node* pntr){
	prop(i, s, e);
	//find count here
	if(DEBUG) cerr<<"PRO "<<s<<" "<<e<<" "<<indx<<" "<<rem<<" "<<k<<endl;
	if(e < indx) return 0;
	if(rem <= 0) return 0;
	if(DEBUG) cerr<<"PRN: "<<pntr<<endl;
	int v = pntr->sum - t[i];
	if(DEBUG) cerr<<" V: "<<v<<endl;
	if(v <= rem && s >= indx){
		//mark them all
		lazy[i] = k;
		prop(i, s, e);
		return v;
	}
	int m = (s + e)/2;
	int done = pro(i*2, s, m, indx,  rem, k, pntr->l);
	done += pro(i*2+1, m+1, e, indx, rem - done, k, pntr->r);
	t[i] = t[i*2] + t[i*2+1];
	return done;
}

void clr(){
	lazy[1] = INF;
}

void print(node* i, int s, int e){
	if(s == e){
		cerr<<" N: "<<i<<" "<<s<<" : "<<i->sum<<endl;
		return;
	}
	int m = (s + e)/2;
	print(i->l, s, m);
	print(i->r, m+1, e);
}


vector<pair<int, int> > a;

void init(int N, int A[], int B[]) {
	if(DEBUG) cerr<<"INIT STARTED"<<endl;
	n = N;
	a.resize(n);
	for(int i = 0; i < n; i++){
		a[i] = {B[i]-1, A[i]-1};
	}

	sort(a.begin(), a.end());
	vector<vector<int> > f(n);
	for(int i = 0; i < n; i++){
		f[a[i].second].push_back(i);
	}

	t = vector<int>(4*n, 0);
	lazy = vector<int>(4*n, -1);
	node* beg = build(0, n-1);
	roots = vector<node*>(n);
	for(int i = 0; i < n; i++){
		if(i)roots[i] = roots[i-1];
		else roots[i] = beg;
		for(int u: f[i]){
			roots[i] = upd(roots[i], 0, n-1, u, 1);
		}
		
		//print(roots[i], 0, n-1);
	}
	if(DEBUG) cerr<<"INIT ENDED"<<endl;
}

int can(int M, int K[]) {
	if(DEBUG) cerr<<"DOING QUERY "<<endl;
	vector<int> q(M);
	for(int i = 0; i < M; i++){
		q[i] = K[i];
	}

	sort(q.begin(), q.end());
	clr();
	bool bad = false;
	for(int u: q){

		//need to find left indxe
		int lo = 0, hi = n-1, mid;
		while(lo < hi){
			mid = (lo + hi)/2;

			if(a[mid].first >= u-1){ //its good
				hi = mid;
			}else{
				lo = mid+1;
			}
		}
		mid = (lo + hi)/2;
		if(a[mid].first < u-1){
			bad = true; break;
		}

		int done = pro(1, 0, n-1, mid, u, u-1, roots[u-1]);
		if(done < u) {
			bad = true;
			break;
		}
	}
	if(DEBUG) cerr<<"DONE"<<endl;
	return bad?0:1;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 3 ms 352 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 356 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 420 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 372 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 296 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 256 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 71740 KB Output is correct
2 Correct 270 ms 72744 KB Output is correct
3 Correct 240 ms 72756 KB Output is correct
4 Correct 214 ms 72952 KB Output is correct
5 Correct 140 ms 71160 KB Output is correct
6 Correct 140 ms 71124 KB Output is correct
7 Correct 137 ms 71180 KB Output is correct
8 Correct 138 ms 71184 KB Output is correct
9 Correct 233 ms 71024 KB Output is correct
10 Correct 158 ms 70768 KB Output is correct
11 Correct 140 ms 70888 KB Output is correct
12 Correct 134 ms 70896 KB Output is correct
13 Correct 146 ms 71412 KB Output is correct
14 Correct 149 ms 71796 KB Output is correct
15 Correct 197 ms 72568 KB Output is correct
16 Correct 196 ms 72540 KB Output is correct
17 Correct 138 ms 71440 KB Output is correct
18 Correct 138 ms 71364 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 71940 KB Output is correct
2 Correct 218 ms 73080 KB Output is correct
3 Correct 713 ms 73192 KB Output is correct
4 Correct 221 ms 72952 KB Output is correct
5 Correct 484 ms 71356 KB Output is correct
6 Correct 455 ms 71428 KB Output is correct
7 Correct 146 ms 71416 KB Output is correct
8 Correct 372 ms 71416 KB Output is correct
9 Correct 229 ms 71152 KB Output is correct
10 Correct 290 ms 70808 KB Output is correct
11 Correct 315 ms 71048 KB Output is correct
12 Correct 560 ms 71152 KB Output is correct
13 Correct 802 ms 71596 KB Output is correct
14 Correct 823 ms 72696 KB Output is correct
15 Correct 349 ms 72696 KB Output is correct
16 Correct 359 ms 72756 KB Output is correct
17 Correct 328 ms 71548 KB Output is correct
18 Correct 334 ms 71604 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1453 ms 392596 KB Output is correct
2 Correct 1424 ms 398840 KB Output is correct
3 Correct 2939 ms 399032 KB Output is correct
4 Correct 1560 ms 398940 KB Output is correct
5 Correct 1758 ms 389904 KB Output is correct
6 Correct 1867 ms 389996 KB Output is correct
7 Correct 762 ms 389992 KB Output is correct
8 Correct 1584 ms 390088 KB Output is correct
9 Correct 1305 ms 389860 KB Output is correct
10 Correct 1138 ms 387816 KB Output is correct
11 Correct 1552 ms 388404 KB Output is correct
12 Correct 1766 ms 388960 KB Output is correct
13 Correct 2765 ms 391732 KB Output is correct
14 Correct 2985 ms 397608 KB Output is correct
15 Correct 1581 ms 397308 KB Output is correct
16 Correct 1569 ms 397240 KB Output is correct
17 Correct 1302 ms 391616 KB Output is correct
18 Correct 1346 ms 391584 KB Output is correct