Submission #129849

#	Time	Username	Problem	Language	Result	Execution time	Memory
129849		hamzqq9	Teams (IOI15_teams)	C++14	0 / 100	363 ms	98132 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007 
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

struct ask {

	int suf;
	int l,r;

}; 

int D;
int tot;
int show[500005];
int P[M],l[M],r[M];
vector<int> root;

ii query(int node,int alt,int bas,int son,int x,int y,int need) {

	if(bas>y || son<x) return {0,-1};

	if(bas>=x && son<=y) {

		if(P[node]-P[alt]<need) return {P[node]-P[alt],-1};

		if(bas==son) return {1,bas};

	}

	ii res=query(l[node],l[alt],bas,orta,x,y,need);

	if(res.nd==-1) {

		need-=res.st;

		return query(r[node],r[alt],orta+1,son,x,y,need);

	}

	return res;

}

int get(int node,int alt,int bas,int son,int x,int y) {

	if(x>y) return 0;
	if(bas>y || son<x) return 0;
	if(bas>=x && son<=y) return P[node]-P[alt];

	return get(l[node],l[alt],bas,orta,x,y)+get(r[node],r[alt],orta+1,son,x,y);

} 

void up(int& node,int& alt,int bas,int son,int pos) {

	if(!node || node==alt) {

		node=++tot;

	}

	if(bas==pos && son==pos) {

		P[node]=P[alt]+1;

		return ;

	}

	if(orta>=pos) {

		if(!r[node]) r[node]=r[alt];

		up(l[node],l[alt],bas,orta,pos);

	}
	else {

		if(!l[node]) l[node]=l[alt];

		up(r[node],r[alt],orta+1,son,pos);

	}

	P[node]=P[l[node]]+P[r[node]];

}

void build(int& node,int bas,int son) {

	if(!node) node=++tot;

	if(bas==son) {

		P[node]=0;

		return ;

	}

	build(l[node],bas,orta);
	build(r[node],orta+1,son);

	P[node]=P[l[node]]+P[r[node]];

}

void init(int N, int A[], int B[]) {

	vector<vector<int>> le=vector<vector<int>>(N+1);
	root=vector<int>(N+1);

	vector<ii> cmp;

	for(int i=0;i<N;i++) {

		cmp.pb({B[i],i});

	}

	for(int i=1;i<=N;i++) {

		cmp.pb({i,-1});

	}

	sort(all(cmp),[&](ii a,ii b) {

		if(a.st<b.st) return true;
		if(a.st>b.st) return false;

		if(a.nd==-1) return true;
		if(b.nd==-1) return false;

		return A[a.nd]<A[b.nd];

	});

	for(int i=0;i<sz(cmp);i++) {

		//cerr<<cmp[i].st<<" "<<cmp[i].nd<<"\n";

		if(cmp[i].nd==-1) {

			show[cmp[i].st]=i+1;

		}
		else {

			B[cmp[i].nd]=i+1;

		}

	}

	for(int i=0;i<N;i++) {

		le[A[i]].pb(B[i]);

	}

	D=sz(cmp);

	build(root[0],1,D);

	for(int i=1;i<=N;i++) {

		if(!sz(le[i])) root[i]=root[i-1];

	//	cerr<<"PUSHED\n";

		for(int x:le[i]) {

	//		cerr<<i<<" "<<x<<"\n";

			up(root[i],root[i-1],1,D,x);

		}

	//	cerr<<"PUSHED\n";

	}

	//cerr<<"WHAT IS : "<<get(root[2],root[0],1,D,2,8)<<"\n";

}

int can(int SZ, int K[]) {

	sort(K,K+SZ);

	vector<ask> s;

	s.pb({D+1,0,0});

	for(int i=0;i<SZ;i++) {

		int need=K[i];

		while(i+1<SZ && K[i]==K[i+1]) i++,need+=K[i];

		ask cur={show[K[i]],s.back().r+1,K[i]};

		while(s.back().suf<=cur.suf) {

			cur.l=s.back().l;

			s.ppb();

		}

		s.pb(cur);

		bool flag=0;

		while(sz(s)>1) {

			ask last=s.back();

			s.ppb();

			ask last2=s.back();

			s.ppb();

			int cnt=get(root[last.r],root[last.l-1],1,D,last.suf,last2.suf-1);

//			cerr<<"CNT IS : "<<cnt<<"\n";
//			cerr<<"l r is : "<<last.suf<<" "<<last2.suf-1<<"\n";


			if(cnt>need) {

				flag=1;
				s.pb(last2);
				s.pb(last);

				break ;

			}
			else {

				need-=cnt;

				last2.r=last.r;

				s.pb(last2);

			}

			if(need==0) break ;

		}

//		cerr<<need<<"\n";

		if(!need) continue ;

		if(!flag) {
	/*cerr<<"--------------\n";*/return 0;}

		ask last=s.back();
		
		s.ppb();

		ii res=query(root[last.r],root[last.l-1],1,D,last.suf,s.back().suf-1,need);

		last.suf=res.nd+1;

		s.pb(last);

	}

//	cerr<<"--------------\n";

	return 1;

}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23