Submission #863764

#	Time	Username	Problem	Language	Result	Execution time	Memory
863764		sunwukong123	Teams (IOI15_teams)	C++14	0 / 100	3233 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;
map<int,int>mpx,mpy;
void init(int N, int A[], int B[]) {

	n=N;
	vector<pi> va, vb;
	for(int i=0;i<n;i++){
		va.push_back({A[i],i});
		vb.push_back({B[i],i});
	}
	sort(va.begin(),va.end());
	sort(vb.begin(),vb.end());
	for(int i=0;i<(int)va.size();i++){
		A[va[i].second]=i+1;
		mpx[va[i].first]=i+1;
	}
	for(int i=1;i<=n;i++){
		auto it=mpx.lower_bound(i);
		if(it->first != i && it != mpx.begin()){
			mpx[i]=prev(it)->second;
		}
	}
	for(int i=1;i<=n;i++){
		auto it=mpy.lower_bound(i);
		if(it->first != i && it != mpy.begin()){
			mpy[i]=prev(it)->second;
		}
	}
	for(int i=(int)vb.size()-1;i>=0;i--){
		B[vb[i].second]=i+1;
		mpy[vb[i].first]=i+1;
	}


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

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

	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=mpx[l.first],y=mpy[l.first],freq=l.second*l.first;
		bool done=0;
		//debug(x,y,freq);
		while(stk.size()){
			//debug(freq);
			pi cur=stk.top();
			int lf=cur.first;
			int top=cur.second;
			//debug(lf,top);

			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});
				if(newx != mpx[l.first] && newy != mpy[l.first])stk.push({newx+1,newy-1});
				//debug(newx,newy);
				break;
			}
		}
		if(done==0)return 0;
	}

	return 1;
}

Compilation message (stderr)

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

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