Submission #288429

#	Time	Username	Problem	Language	Result	Execution time	Memory
288429		kshitij_sodani	Teams (IOI15_teams)	C++14	77 / 100	4045 ms	183800 KiB

teams

#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define a first
#define b second
#define pb push_back
#define mp make_pair

#include "teams.h"
int n;
int aa[500001];
int bb[500001];
vector<int> su[500001];
int tree[30*500001];
int l[30*500001];
int r[30*500001];
int root=0;
int dp[500001];

int lab[500001];
int cnt=0;
vector<int> xx[500001];
void build(int no,int ll,int rr){
	cnt=max(cnt,no);
	if(ll==rr){
		tree[no]=0;
	}
	else{
		int mid=(ll+rr)/2;
		build(no*2+1,ll,mid);
		build(no*2+2,mid+1,rr);
		tree[no]=0;
		l[no]=no*2+1;
		r[no]=no*2+2;
	}
}
int update(int no,int ll,int rr,int ind){

	if(ll==rr){
		cnt++;
		tree[cnt]=tree[no]+1;
		return cnt;
	}
	else{
		int mid=(ll+rr)/2;
		cnt++;
		int cur=cnt;
		if(ind<=mid){
			l[cur]=update(l[no],ll,mid,ind);
			r[cur]=r[no];
		}
		else{
			r[cur]=update(r[no],mid+1,rr,ind);
			l[cur]=l[no];
		}
		tree[cur]=tree[l[cur]]+tree[r[cur]];

		return cur;
	}
}
void init(int nn, int A[], int B[]) {
	n=nn;
	for(int i=0;i<n;i++){
		aa[i]=A[i];
		bb[i]=B[i];
		su[bb[i]].pb(aa[i]);
		xx[aa[i]].pb(bb[i]);
	}
	build(0,0,n-1);
	for(int i=n;i>=1;i--){
		for(auto j:su[i]){
			root=update(root,0,n-1,j-1);

		}
		lab[i]=root;
	}

}
int query(int no,int ll,int rr,int aa,int bb){
	if(rr<aa or ll>bb or aa>bb){
		return 0;
	}
	if(aa<=ll and rr<=bb){
		//cout<<ll<<"..."<<rr<<endl;
		return tree[no];
	}
	else{
		int mid=(ll+rr)/2;
		return query(l[no],ll,mid,aa,bb)+query(r[no],mid+1,rr,aa,bb);
	}
}

int can(int m, int k[]){
	
	if(m>300){
		int so=0;;
		for(int i=0;i<m;i++){
			xx[k[i]].pb(n+1);
			so+=k[i];
		}
		if(so>n){
			return 0;
		}
		priority_queue<int> cur;
		for(int i=1;i<=n;i++){
			for(auto j:xx[i]){
				if(j==n+1){
					while(cur.size() and -cur.top()<i){
						cur.pop();
					}
					for(int kk=0;kk<i;kk++){
						if(cur.size()==0){
							for(int ii=0;ii<m;ii++){
								xx[k[ii]].pop_back();
							}
							return 0;
						}
						cur.pop();
					}
				}
				else{
					cur.push(-j);
				}
			}
		}
		for(int i=0;i<m;i++){
			xx[k[i]].pop_back();
		}
		return 1;
	}
	sort(k,k+m);
	for(int i=0;i<m;i++){
		dp[i]=query(lab[k[i]],0,n-1,0,k[i]-1)-k[i];
		for(int j=0;j<i;j++){
			dp[i]=min(dp[i],dp[j]+query(lab[k[i]],0,n-1,k[j],k[i]-1)-k[i]);
		}
		if(dp[i]<0){
			return 0;
		}
	}
	return 1;

}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:79:45: warning: declaration of 'bb' shadows a global declaration [-Wshadow]
   79 | int query(int no,int ll,int rr,int aa,int bb){
      |                                             ^
teams.cpp:12:5: note: shadowed declaration is here
   12 | int bb[500001];
      |     ^~
teams.cpp:79:45: warning: declaration of 'aa' shadows a global declaration [-Wshadow]
   79 | int query(int no,int ll,int rr,int aa,int bb){
      |                                             ^
teams.cpp:11:5: note: shadowed declaration is here
   11 | int aa[500001];
      |     ^~

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