Submission #288376

#	Time	Username	Problem	Language	Result	Execution time	Memory
288376		kshitij_sodani	Teams (IOI15_teams)	C++14	21 / 100	4080 ms	157432 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[8*500001];
int l[8*500001];
int r[8*500001];
int root=0;
int dp[500001];

int lab[500001];
int cnt=0;
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;
		//cout<<ll<<"<<"<<tree[cnt]<<endl;
		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]);
	}
	//cout<<22<<endl;
	build(0,0,n-1);
	for(int i=n;i>=1;i--){
		for(auto j:su[i]){
		//	cout<<i<<":"<<j<<endl;
			root=update(root,0,n-1,j-1);

		}
		lab[i]=root;
		//cout<<lab[i]<<"/"<<endl;
	}
	//cout<<endl;
	//cout<<11<<endl;
}
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[]){
	sort(k,k+m);
/*	vector<pair<int,int>> xx;
	for(int i=0;i<n;i++){
		xx.pb({aa[i],bb[i]});
	}
	for(int i=0;i<m;i++){
		xx.pb({k[i],n+1});
	}
	sort(xx.begin(),xx.end());
	multiset<int> cur;
	for(auto j:xx){
		if(j.b==n+1){
			while(cur.size()){
				if(*(cur.begin())<j.a){
					cur.erase(cur.begin());
				}
				else{
					break;
				}
			}
			for(int k=0;k<j.a;k++){
				if(cur.size()==0){
					return 0;
				}
				cur.erase(cur.begin());
			}
		}
		else{
			cur.insert(j.b);
		}
	}*/
	if(true){
		for(int i=0;i<m;i++){
			//cout<<lab[k[i]]<<"::"<<0<<"::"<<k[i]-1<<endl;
			//cout<<query(lab[k[i]],0,n-1,0,k[i]-1)<<endl;
			dp[i]=query(lab[k[i]],0,n-1,0,k[i]-1)-k[i];
			//cout<<dp[i]<<"::"<<endl;
			for(int j=0;j<i;j++){
			//	cout<<query(lab[k[i]],0,n-1,k[j],k[i]-1)<<":"<<k[j]<<":"<<k[i]-1<<endl;
				dp[i]=min(dp[i],dp[j]+query(lab[k[i]],0,n-1,k[j],k[i]-1)-k[i]);
			}
		//	cout<<i<<"//"<<dp[i]<<",,"<<endl;
			if(dp[i]<0){
				return 0;
			}
		}

	}
	return 1;

}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:82:45: warning: declaration of 'bb' shadows a global declaration [-Wshadow]
   82 | 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:82:45: warning: declaration of 'aa' shadows a global declaration [-Wshadow]
   82 | 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: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23