Submission #129997

#	Time	Username	Problem	Language	Result	Execution time	Memory
129997		Adhyyan1252	Teams (IOI15_teams)	C++11	100 / 100	2985 ms	399032 KiB

teams

#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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23