oj.uz

Submission #640001

# Submission time Handle Problem Language Result Execution time Memory
640001 2022-09-13T07:28:15 Z ggoh Teams (IOI15_teams) C++14
100 / 100
 2932 ms 168228 KB 
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
int n,sz;
vector<int>G[500005];
struct PST{
	int l,r,val;
}T[11000000];
int root[500005];
void initree(int num,int s,int e)
{
	if(s==e)return ;
	T[num].l=sz;
	T[sz++]={-1,-1,0};
	T[num].r=sz;
	T[sz++]={-1,-1,0};
	initree(T[num].l,s,(s+e)/2);
	initree(T[num].r,(s+e)/2+1,e);
}
void update(int par,int num,int s,int e,int x)
{
	T[num].val=T[par].val+1;
	if(s==e)return ;
	if(x<=(s+e)/2)
	{
		T[num].r=T[par].r;
		T[num].l=sz;
		T[sz++]={-1,-1,0};
		update(T[par].l,T[num].l,s,(s+e)/2,x);
	}
	else
	{
		T[num].l=T[par].l;
		T[num].r=sz;
		T[sz++]={-1,-1,0};
		update(T[par].r,T[num].r,(s+e)/2+1,e,x);
	}
}
struct D{
	int A,B;
}d[500005];
int go[500005];
bool cmp(D a,D b){return a.B<b.B;}
void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0;i<n;i++)
	{
		d[i]={A[i],B[i]};
		go[i+1]=1e9;
	}
	sort(d,d+n,cmp);
	for(int i=0;i<n;i++)
	{
		go[d[i].B]=min(go[d[i].B],i+1);
		G[d[i].A].push_back(i+1);
	}
	for(int i=n-1;i>=1;i--)go[i]=min(go[i],go[i+1]);
	root[0]=sz;
	T[sz++]={-1,-1,0};
	initree(0,1,n);
	for(int i=1;i<=n;i++)
	{
		if(!sz(G[i]))
		{
			root[i]=root[i-1];
			continue;
		}
		int prev=root[i-1];
		for(auto &k:G[i])
		{
			root[i]=sz;
			T[sz++]={-1,-1,0};
			update(prev,root[i],1,n,k);
			prev=root[i];
		}
	}
}
int getsum(int num1,int num2,int s,int e,int x1,int x2)
{
	if(s>x2||x1>e)return 0;
	if(x1<=s&&e<=x2)return T[num2].val-T[num1].val;
	return getsum(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2)+getsum(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
}
int getx(int x1,int x2,int y1,int y2)
{
	return getsum(root[y1-1],root[y2],1,n,x1,x2);
}
int rem[200002];
int can(int M, int K[]) {
	
	lint sum=0;
	for(int i=0;i<M;i++)sum+=K[i];
	if(sum>n)return 0;
	int ans=1,t;
	sort(K,K+M);
	t=K[0];
	vector<pii>V;
	for(int i=1;i<M;i++)
	{
		if(K[i]==K[i-1])
		{
			t+=K[i];
		}
		else
		{
			V.push_back({K[i-1],t});
			t=K[i];
		}
	}
	V.push_back({K[M-1],t});
	int m=sz(V);
	for(int i=0;i<m;i++)rem[i]=V[i].second;
	for(int i=m-1;i>=0;i--)
	{
		int r=0;
		for(int j=m-1;j>=i+1;j--)
		{
			if(!rem[j])continue;
			t=getx(go[V[j].first],n,i==0?1:(V[i-1].first+1),V[i].first)-r;
			if(rem[j]<t)t=rem[j];
			r+=t;
			rem[j]-=t;
		}
		t=getx(go[V[i].first],n,i==0?1:(V[i-1].first+1),V[i].first)-r;
		if(rem[i]<t)t=rem[i];
		rem[i]-=t;
	}
	for(int i=0;i<m;i++)if(rem[i])ans=0;
	return ans;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 39240 KB Output is correct
2 Correct 74 ms 39268 KB Output is correct
3 Correct 62 ms 39240 KB Output is correct
4 Correct 67 ms 39612 KB Output is correct
5 Correct 37 ms 38100 KB Output is correct
6 Correct 41 ms 38108 KB Output is correct
7 Correct 38 ms 38108 KB Output is correct
8 Correct 40 ms 38100 KB Output is correct
9 Correct 34 ms 37956 KB Output is correct
10 Correct 33 ms 37952 KB Output is correct
11 Correct 34 ms 37964 KB Output is correct
12 Correct 37 ms 38024 KB Output is correct
13 Correct 51 ms 38220 KB Output is correct
14 Correct 52 ms 38576 KB Output is correct
15 Correct 60 ms 39116 KB Output is correct
16 Correct 62 ms 39108 KB Output is correct
17 Correct 39 ms 38052 KB Output is correct
18 Correct 39 ms 37964 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 39664 KB Output is correct
2 Correct 190 ms 39620 KB Output is correct
3 Correct 139 ms 42620 KB Output is correct
4 Correct 61 ms 39628 KB Output is correct
5 Correct 80 ms 38412 KB Output is correct
6 Correct 94 ms 38396 KB Output is correct
7 Correct 83 ms 38468 KB Output is correct
8 Correct 93 ms 38416 KB Output is correct
9 Correct 33 ms 37952 KB Output is correct
10 Correct 36 ms 38320 KB Output is correct
11 Correct 40 ms 38332 KB Output is correct
12 Correct 1006 ms 38604 KB Output is correct
13 Correct 191 ms 38732 KB Output is correct
14 Correct 164 ms 40908 KB Output is correct
15 Correct 87 ms 39616 KB Output is correct
16 Correct 95 ms 39684 KB Output is correct
17 Correct 60 ms 38348 KB Output is correct
18 Correct 70 ms 38332 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 162388 KB Output is correct
2 Correct 2673 ms 162504 KB Output is correct
3 Correct 707 ms 168228 KB Output is correct
4 Correct 466 ms 162536 KB Output is correct
5 Correct 304 ms 156120 KB Output is correct
6 Correct 382 ms 156124 KB Output is correct
7 Correct 308 ms 156072 KB Output is correct
8 Correct 408 ms 156032 KB Output is correct
9 Correct 158 ms 155332 KB Output is correct
10 Correct 157 ms 155324 KB Output is correct
11 Correct 1573 ms 155484 KB Output is correct
12 Correct 2932 ms 155596 KB Output is correct
13 Correct 818 ms 157068 KB Output is correct
14 Correct 700 ms 164228 KB Output is correct
15 Correct 410 ms 161020 KB Output is correct
16 Correct 448 ms 161100 KB Output is correct
17 Correct 235 ms 155748 KB Output is correct
18 Correct 245 ms 155896 KB Output is correct