Submission #863762

#	Time	Username	Problem	Language	Result	Execution time	Memory
863762		sunwukong123	Teams (IOI15_teams)	C++14	0 / 100	2929 ms	524288 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std; 

void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

struct node2 {
	int s,e,m,val;
	node2 *l, *r;
	node2(int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=0;
		l=r=nullptr;
	}
	node2* update(int x, int nval){ // point add, range query
		node2* curnode=new node2(s,e);curnode->val=val;
		if(l==nullptr){
			l=new node2(s,m);
		}
		if(r==nullptr){
			r=new node2(m+1,e);
		}
		if(s==e){
			
			curnode->val+=nval;
			return curnode;
		}
		if(x>m){
			node2* newr=r->update(x,nval);
			curnode->r=newr;
			curnode->l=l;
			curnode->val=curnode->r->val+curnode->l->val;
			return curnode;
		} else{
			node2* newl=l->update(x,nval);
			curnode->l=newl;
			curnode->r=r;
			curnode->val=curnode->r->val+curnode->l->val;
			return curnode;
		}
	} 
	int query(int x, int y){
		if(x>y)return 0;
		if(s==x&&e==y)return val;
		if(x>m)return r?r->query(x,y):0;
		else if(y<=m)return l?l->query(x,y):0;
		else return (l?l->query(x,m):0) + (r?r->query(m+1,y):0);
	}

} *segx[MAXN],*segy[MAXN];;
int n;
void init(int N, int A[], int B[]) {

	n=N;

	vector<int> Vx[n+5];
	vector<int> Vy[n+5];

	for(int i=1;i<=n;i++){
		Vx[A[i-1]].push_back(B[i-1]);
		Vy[B[i-1]].push_back(A[i-1]);
	}
	/*

	for(int i=1;i<=n;i++){
		sort(Vx[i].begin(),Vx[i].end());
		sort(Vy[i].begin(),Vy[i].end());
	}*/
	segy[0]=new node2(0,n);
	segx[0]=new node2(0,n);

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

		segx[i]=segx[i-1];
		for(auto x:Vx[i]){
			segx[i]=segx[i]->update(x,1);
		}
	}
	for(int i=1;i<=n;i++){
		segy[i]=segy[i-1];
		for(auto x:Vy[i]){
			segy[i]=segy[i]->update(x,1);
		}
	}

}
int Lkth(node2* s2, node2* s1, int k){
	if(s2->s == s2->e){
		return s2->s;
	}
	int R2=s2->r?s2->r->val:0;
	int L2=s2->l?s2->l->val:0;

	int R1=s1->r?s1->r->val:0;
	int L1=s1->l?s1->l->val:0;

	int rval=R2-R1;
	int lval=L2-L1;
	if(lval>=k){
		if(s2->l==nullptr)s2->l=new node2(s2->s,s2->m);
		if(s1->l==nullptr)s1->l=new node2(s1->s,s1->m);
		return Lkth(s2->l, s1->l, k);
	}
	else {
		if(s2->r==nullptr)s2->r=new node2(s2->m+1,s2->e);
		if(s1->r==nullptr)s1->r=new node2(s1->m+1,s1->e);
		return Lkth(s2->r,s1->r,k-lval);
	}
}
int Rkth(node2* s2, int k){
	if(s2->s == s2->e){
		return s2->s;
	}
	int rval=s2->r?s2->r->val:0;
	int lval=s2->l?s2->l->val:0;

	if(lval>=k){
		if(s2->l==nullptr)s2->l=new node2(s2->s,s2->m);
		
		return Rkth(s2->l,k);
		
	}
	else {
		if(s2->r==nullptr)s2->r=new node2(s2->m+1,s2->e);
		return Rkth(s2->r,k-lval);
	}
}
int can(int m, int K[]) {
	map<int,int> mp;
	int tot=0;
	for(int i=0;i<m;i++){
		mp[K[i]]++;
		tot+=K[i];
	}
	if(tot>n)return 0;
	stack<pi> stk; // 
	stk.push({0,n});
	for(auto l:mp){
		int x=l.first,y=l.first,freq=l.second;
		bool done=0;
		while(stk.size()){
			pi cur=stk.top();
			int lf=cur.first;
			int top=cur.second;

			int S=segx[x]->query(y,top) - segx[lf]->query(y,top);

			if(S<freq){
				freq-=S;
				y=top+1;
				stk.pop();
			} else{
				done=1;
				int b=segx[x]->query(0,y) - segx[lf]->query(0,y);
				int newy=Lkth(segx[lf], segx[x], b+freq);
				//find the smallest Y that is OK
				int need=freq-(segx[x]->query(y,newy-1) - segx[lf]->query(y,newy-1));

				int e=segy[newy]->query(0,lf);
				int newx=Rkth(segy[newy],e+need);
				stk.push({newx,newy});
				break;
			}
		}
		if(done==0)return 0;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int Lkth(node2*, node2*, int)':
teams.cpp:108:6: warning: unused variable 'rval' [-Wunused-variable]
  108 |  int rval=R2-R1;
      |      ^~~~
teams.cpp: In function 'int Rkth(node2*, int)':
teams.cpp:125:6: warning: unused variable 'rval' [-Wunused-variable]
  125 |  int rval=s2->r?s2->r->val:0;
      |      ^~~~

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