oj.uz

Submission #863788

# Submission time Handle Problem Language Result Execution time Memory
863788 2023-10-21T03:58:26 Z sunwukong123 Teams (IOI15_teams) C++14
77 / 100
 1037 ms 524288 KB 
#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;
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;
		}
		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]);
	}
 
 
	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;
}

Compilation message

teams.cpp: In function 'int Lkth(node2*, node2*, int)':
teams.cpp:150:6: warning: unused variable 'rval' [-Wunused-variable]
  150 |  int rval=R2-R1;
      |      ^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 233172 KB Output is correct
2 Correct 322 ms 232972 KB Output is correct
3 Correct 308 ms 233152 KB Output is correct
4 Correct 312 ms 233112 KB Output is correct
5 Correct 250 ms 233176 KB Output is correct
6 Correct 251 ms 233148 KB Output is correct
7 Correct 254 ms 233180 KB Output is correct
8 Correct 247 ms 233168 KB Output is correct
9 Correct 207 ms 233168 KB Output is correct
10 Correct 221 ms 233388 KB Output is correct
11 Correct 214 ms 233152 KB Output is correct
12 Correct 219 ms 233144 KB Output is correct
13 Correct 283 ms 233028 KB Output is correct
14 Correct 262 ms 233144 KB Output is correct
15 Correct 294 ms 233148 KB Output is correct
16 Correct 291 ms 233164 KB Output is correct
17 Correct 243 ms 233152 KB Output is correct
18 Correct 256 ms 233152 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 233148 KB Output is correct
2 Correct 322 ms 233156 KB Output is correct
3 Correct 787 ms 233148 KB Output is correct
4 Correct 318 ms 233152 KB Output is correct
5 Correct 420 ms 233100 KB Output is correct
6 Correct 405 ms 233108 KB Output is correct
7 Correct 264 ms 233152 KB Output is correct
8 Correct 371 ms 233028 KB Output is correct
9 Correct 213 ms 233152 KB Output is correct
10 Correct 226 ms 233064 KB Output is correct
11 Correct 242 ms 232996 KB Output is correct
12 Correct 624 ms 233148 KB Output is correct
13 Correct 963 ms 233152 KB Output is correct
14 Correct 981 ms 233148 KB Output is correct
15 Correct 383 ms 233148 KB Output is correct
16 Correct 393 ms 233364 KB Output is correct
17 Correct 336 ms 233152 KB Output is correct
18 Correct 324 ms 233328 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1037 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -