oj.uz

Submission #288429

# Submission time Handle Problem Language Result Execution time Memory
288429 2020-09-01T13:34:34 Z kshitij_sodani Teams (IOI15_teams) C++14
77 / 100
 4000 ms 183800 KB 
#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

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.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 52284 KB Output is correct
2 Correct 116 ms 52344 KB Output is correct
3 Correct 109 ms 52220 KB Output is correct
4 Correct 114 ms 53308 KB Output is correct
5 Correct 47 ms 49784 KB Output is correct
6 Correct 50 ms 49868 KB Output is correct
7 Correct 46 ms 49912 KB Output is correct
8 Correct 46 ms 49784 KB Output is correct
9 Correct 50 ms 50924 KB Output is correct
10 Correct 50 ms 50668 KB Output is correct
11 Correct 49 ms 50540 KB Output is correct
12 Correct 48 ms 49984 KB Output is correct
13 Correct 60 ms 50160 KB Output is correct
14 Correct 67 ms 50920 KB Output is correct
15 Correct 103 ms 52088 KB Output is correct
16 Correct 102 ms 52088 KB Output is correct
17 Correct 50 ms 50168 KB Output is correct
18 Correct 51 ms 50168 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 52600 KB Output is correct
2 Correct 116 ms 52600 KB Output is correct
3 Correct 230 ms 55648 KB Output is correct
4 Correct 114 ms 53236 KB Output is correct
5 Correct 577 ms 50296 KB Output is correct
6 Correct 897 ms 50296 KB Output is correct
7 Correct 49 ms 50296 KB Output is correct
8 Correct 655 ms 50292 KB Output is correct
9 Correct 50 ms 51820 KB Output is correct
10 Correct 71 ms 51868 KB Output is correct
11 Correct 283 ms 52036 KB Output is correct
12 Correct 2067 ms 51612 KB Output is correct
13 Correct 417 ms 51952 KB Output is correct
14 Correct 263 ms 55544 KB Output is correct
15 Correct 227 ms 53880 KB Output is correct
16 Correct 219 ms 53880 KB Output is correct
17 Correct 328 ms 51960 KB Output is correct
18 Correct 339 ms 51960 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 177820 KB Output is correct
2 Correct 828 ms 177784 KB Output is correct
3 Correct 1156 ms 183800 KB Output is correct
4 Correct 821 ms 179188 KB Output is correct
5 Correct 2664 ms 165536 KB Output is correct
6 Execution timed out 4045 ms 167616 KB Time limit exceeded
7 Halted 0 ms 0 KB -