oj.uz

Submission #863785

# Submission time Handle Problem Language Result Execution time Memory
863785 2023-10-21T03:53:46 Z sunwukong123 Teams (IOI15_teams) C++14
77 / 100
 1895 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 = 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;
		}
		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){
		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 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:148:6: warning: unused variable 'rval' [-Wunused-variable]
  148 |  int rval=R2-R1;
      |      ^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 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 2396 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 2496 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2652 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 2392 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 342 ms 229240 KB Output is correct
2 Correct 364 ms 229120 KB Output is correct
3 Correct 326 ms 229164 KB Output is correct
4 Correct 322 ms 228976 KB Output is correct
5 Correct 268 ms 229208 KB Output is correct
6 Correct 266 ms 229148 KB Output is correct
7 Correct 255 ms 229820 KB Output is correct
8 Correct 258 ms 229820 KB Output is correct
9 Correct 236 ms 229920 KB Output is correct
10 Correct 225 ms 229772 KB Output is correct
11 Correct 224 ms 229640 KB Output is correct
12 Correct 227 ms 229908 KB Output is correct
13 Correct 312 ms 229952 KB Output is correct
14 Correct 273 ms 230076 KB Output is correct
15 Correct 316 ms 230476 KB Output is correct
16 Correct 304 ms 230272 KB Output is correct
17 Correct 268 ms 230292 KB Output is correct
18 Correct 264 ms 230080 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 229052 KB Output is correct
2 Correct 343 ms 229104 KB Output is correct
3 Correct 827 ms 229048 KB Output is correct
4 Correct 322 ms 229044 KB Output is correct
5 Correct 445 ms 228992 KB Output is correct
6 Correct 414 ms 229076 KB Output is correct
7 Correct 283 ms 230320 KB Output is correct
8 Correct 377 ms 230012 KB Output is correct
9 Correct 223 ms 230368 KB Output is correct
10 Correct 235 ms 229816 KB Output is correct
11 Correct 250 ms 229824 KB Output is correct
12 Correct 636 ms 230076 KB Output is correct
13 Correct 1024 ms 230344 KB Output is correct
14 Correct 1008 ms 230432 KB Output is correct
15 Correct 401 ms 230396 KB Output is correct
16 Correct 398 ms 230584 KB Output is correct
17 Correct 329 ms 230332 KB Output is correct
18 Correct 326 ms 230324 KB Output is correct

Subtask #4
0 / 23.0

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