제출 #863789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863789		sunwukong123	팀들 (IOI15_teams)	C++14	77 / 100	1111 ms	524288 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std; 
#ifdef LOCAL
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__)
#else
#define debug(...)
#endif
const int MAXN = 500005;
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,val;
	node2 *l, *r;
	node2(int _s, int _e){
		s=_s;e=_e;
		val=0;
		l=r=nullptr;
	}
	node2* update(int x, int nval){ // point add, range query
		int m=(s+e)/2;
		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){
		int m=(s+e)/2;
		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;
int mpx[MAXN],mpy[MAXN];
void init(int N, int A[], int B[]) {
 	map<int,int>mpx,mpy;
	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;
		}
		debug(i,mpx[i]);
	}
	
	for(int i=(int)vb.size()-1;i>=0;i--){
		B[vb[i].second]=i+1;
		mpy[vb[i].first]=i+1;
	}
	for(int i=1;i<=n;i++){
		auto it=mpy.lower_bound(i);
		if(it==mpy.end()){
			mpy[i]=n;
			continue;
		}

		if(it->first != i){
			mpy[i]=it->second;
		}
		debug(i,mpy[i]);
	}
 
 	for(int i=1;i<=n;i++){
 		::mpx[i]=mpx[i];
 		::mpy[i]=mpy[i];
 	}
 
	vector<int> Vx[n+5];
	vector<int> Vy[n+5];
 
	for(int i=0;i<n;i++){
		debug(A[i],B[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){
		int s2m=(s2->s+s2->e)/2;
		if(s2->l==nullptr)s2->l=new node2(s2->s,s2m);
		int s1m=(s1->s+s1->e)/2;
		if(s1->l==nullptr)s1->l=new node2(s1->s,s1m);
		return Lkth(s2->l, s1->l, k);
	}
	else {
		int s2m=(s2->s+s2->e)/2;
		if(s2->r==nullptr)s2->r=new node2(s2m+1,s2->e);
		int s1m=(s1->s+s1->e)/2;
		if(s1->r==nullptr)s1->r=new node2(s1m+1,s1->e);
		return Lkth(s2->r,s1->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;
		debug(x,y,freq);
		bool done=0;
		while(stk.size()){

			//debug(freq);
			pi cur=stk.top();
			int lf=cur.first;
			int top=cur.second;
			if(top<y){
				stk.pop();
				continue;
			}
 
			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-1) - segx[lf]->query(0,y-1);
				debug(b);
				int newy=Lkth(segx[x], segx[lf], b+freq);
				assert(newy!=0);
				//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)-segy[newy-1]->query(0,lf);
 
				int newx=Lkth(segy[newy],segy[newy-1],e+need);
				debug(need,e,newx);
				stk.push({newx,newy});
				if(newx != mpx[l.first] && newy != mpy[l.first])stk.push({mpx[l.first],newy-1});
				//debug(newx,newy);
				break;
			}
		}
		if(done==0)return 0;
	}
 
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:68:15: warning: declaration of 'mpx' shadows a global declaration [-Wshadow]
   68 |   map<int,int>mpx,mpy;
      |               ^~~
teams.cpp:66:5: note: shadowed declaration is here
   66 | int mpx[MAXN],mpy[MAXN];
      |     ^~~
teams.cpp:68:19: warning: declaration of 'mpy' shadows a global declaration [-Wshadow]
   68 |   map<int,int>mpx,mpy;
      |                   ^~~
teams.cpp:66:15: note: shadowed declaration is here
   66 | int mpx[MAXN],mpy[MAXN];
      |               ^~~
teams.cpp: In function 'int Lkth(node2*, node2*, int)':
teams.cpp:155:6: warning: unused variable 'rval' [-Wunused-variable]
  155 |  int rval=R2-R1;
      |      ^~~~

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