oj.uz

Submission #569733

# Submission time Handle Problem Language Result Execution time Memory
569733 2022-05-27T16:52:19 Z CSQ31 Teams (IOI15_teams) C++17
100 / 100
 1284 ms 414384 KB 
#pragma GCC optimize("Ofast") 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
const int MAXN = 5e5+5;
struct node{
	int x,lf = -1,rg = -1;
	node(){}
};
node T[MAXN*60];
int ccnt = 0;
void pull(int v){
	T[v].x = 0;
	if(T[v].lf!=-1)T[v].x+=T[T[v].lf].x;
	if(T[v].rg!=-1)T[v].x+=T[T[v].rg].x;
}
int copy(int v){
	T[++ccnt] = T[v];
	return ccnt;
}
int newnode(){
	ccnt++;
	T[ccnt].x = 0;
	T[ccnt].lf = T[ccnt].rg = -1;
	return ccnt;
	
}
int add(int v,int l,int r,int pos,int x){
	int me = copy(v);
	if(l==r){
		T[me].x+=x;
		return me;
	}
	int tm = (l+r)/2;
	if(pos<=tm){
		if(T[v].lf == -1)T[v].lf = newnode();
		T[me].lf = add(T[v].lf,l,tm,pos,x);
	}else{
		if(T[v].rg == -1)T[v].rg = newnode();
		T[me].rg = add(T[v].rg,tm+1,r,pos,x);
	}
	pull(me);
	return me;
}
int zero(int used,int l,int r,int tl,int tr){
	int v = copy(used);
	if(l<=tl && tr<=r){
		T[v].x = 0;
		T[v].lf = T[v].rg = -1;
		return v;
	}
	int tm = (tl+tr)/2;
	if(r<=tm){
		if(T[v].lf != -1)T[v].lf = zero(T[used].lf,l,r,tl,tm);
	}
	else if(l >tm){
		if(T[v].rg != -1)T[v].rg = zero(T[used].rg,l,r,tm+1,tr);
	}else{
		if(T[v].lf != -1)T[v].lf = zero(T[used].lf,l,tm,tl,tm);
		if(T[v].rg != -1)T[v].rg = zero(T[used].rg,tm+1,r,tm+1,tr);
	}
	pull(v);
	return v;
}
vector<int>seg;
int n;
bool kek = 1;
int walk(int avi,int used,int l,int r,int k){
	//cout<<l<<" "<<r<<" "<<T[avi].x<<" "<<T[used].x<<" "<<k<<'\n';
	int v = copy(used);
	if(T[avi].x - T[v].x < k || !k){
		kek = 0;
		return v;
	}
	if(l==r){
		T[v].x += k;
		return v;
	}
	int tm = (l+r)/2;
	int val = 0;
	if(T[v].lf == -1)T[v].lf = newnode();
	if(T[v].rg == -1)T[v].rg = newnode();
	if(T[avi].lf != -1)val+=T[T[avi].lf].x;
	val-=T[T[v].lf].x;
	if(val>=k)T[v].lf = walk(T[avi].lf,T[v].lf,l,tm,k);
	else{
		T[v].lf = T[avi].lf;
		T[v].rg = walk(T[avi].rg,T[v].rg,tm+1,r,k-val);
	}
	pull(v);
	return v;
}
void init(int N, int A[], int B[]) {
	n = N;
	seg.push_back(0);
	vector<map<int,int>>cnt(n+1);
	vector<int>cnt1(n+2,0);
	for(int i=0;i<n;i++){
		cnt[A[i]][B[i]]++;
		cnt1[B[i]+1]++;
	}
	for(int i=1;i<=n;i++){
		seg.push_back(copy(seg.back()));
		for(auto x:cnt[i]){
			//cout<<i<<" "<<x.fi<<" "<<x.se<<'\n';
			seg.back() = add(seg.back(),1,n,x.fi,x.se);
		}
		if(cnt1[i])seg.back() = add(seg.back(),1,n,i-1,-cnt1[i]);
	}
}
int can(int m, int K[]) {
	int sum = 0;
	map<int,int>cnt;
	for(int i=0;i<m;i++){
		sum+=K[i];
		cnt[K[i]]++;
		if(sum>n)return 0;
	}
	vector<pii>a;
	for(auto x:cnt)a.push_back(x);
	int old = ccnt;
	int used = newnode();
	kek = 1;
	for(auto x:a){
		//cout<<x.fi<<" "<<x.se<<'\n';
		if(x.fi>1)used = zero(used,1,x.fi-1,1,n);
		used = walk(seg[x.fi],used,1,n,x.fi*x.se);
		if(!kek)break;
	}
	for(int i=old+1;i<=ccnt;i++){
		T[i].x = 0;
		T[i].lf = T[i].rg = -1;
	}
	ccnt = old;
	return kek;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 352520 KB Output is correct
2 Correct 192 ms 352432 KB Output is correct
3 Correct 189 ms 352532 KB Output is correct
4 Correct 207 ms 352528 KB Output is correct
5 Correct 189 ms 352440 KB Output is correct
6 Correct 185 ms 352756 KB Output is correct
7 Correct 200 ms 352460 KB Output is correct
8 Correct 190 ms 352440 KB Output is correct
9 Correct 181 ms 352548 KB Output is correct
10 Correct 194 ms 352516 KB Output is correct
11 Correct 204 ms 352452 KB Output is correct
12 Correct 192 ms 352488 KB Output is correct
13 Correct 193 ms 352564 KB Output is correct
14 Correct 196 ms 352520 KB Output is correct
15 Correct 177 ms 352464 KB Output is correct
16 Correct 184 ms 352588 KB Output is correct
17 Correct 207 ms 352480 KB Output is correct
18 Correct 181 ms 352488 KB Output is correct
19 Correct 182 ms 352476 KB Output is correct
20 Correct 191 ms 352528 KB Output is correct
21 Correct 188 ms 352460 KB Output is correct
22 Correct 184 ms 352604 KB Output is correct
23 Correct 223 ms 352460 KB Output is correct
24 Correct 186 ms 352452 KB Output is correct
25 Correct 188 ms 352532 KB Output is correct
26 Correct 218 ms 352512 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 364904 KB Output is correct
2 Correct 282 ms 364924 KB Output is correct
3 Correct 298 ms 364840 KB Output is correct
4 Correct 298 ms 365100 KB Output is correct
5 Correct 198 ms 359880 KB Output is correct
6 Correct 206 ms 359844 KB Output is correct
7 Correct 196 ms 359752 KB Output is correct
8 Correct 197 ms 359852 KB Output is correct
9 Correct 200 ms 359864 KB Output is correct
10 Correct 195 ms 359500 KB Output is correct
11 Correct 195 ms 359728 KB Output is correct
12 Correct 220 ms 359780 KB Output is correct
13 Correct 207 ms 360812 KB Output is correct
14 Correct 239 ms 362284 KB Output is correct
15 Correct 272 ms 363900 KB Output is correct
16 Correct 252 ms 363976 KB Output is correct
17 Correct 215 ms 360172 KB Output is correct
18 Correct 209 ms 360280 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 365064 KB Output is correct
2 Correct 297 ms 365120 KB Output is correct
3 Correct 402 ms 365060 KB Output is correct
4 Correct 296 ms 365040 KB Output is correct
5 Correct 265 ms 360028 KB Output is correct
6 Correct 252 ms 360008 KB Output is correct
7 Correct 223 ms 359992 KB Output is correct
8 Correct 248 ms 360060 KB Output is correct
9 Correct 213 ms 359808 KB Output is correct
10 Correct 204 ms 359664 KB Output is correct
11 Correct 203 ms 359732 KB Output is correct
12 Correct 259 ms 359876 KB Output is correct
13 Correct 301 ms 361096 KB Output is correct
14 Correct 427 ms 364876 KB Output is correct
15 Correct 309 ms 364188 KB Output is correct
16 Correct 334 ms 364132 KB Output is correct
17 Correct 244 ms 360404 KB Output is correct
18 Correct 254 ms 360428 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 413828 KB Output is correct
2 Correct 999 ms 412500 KB Output is correct
3 Correct 1149 ms 412428 KB Output is correct
4 Correct 933 ms 414384 KB Output is correct
5 Correct 404 ms 388160 KB Output is correct
6 Correct 382 ms 388220 KB Output is correct
7 Correct 281 ms 388128 KB Output is correct
8 Correct 386 ms 388120 KB Output is correct
9 Correct 233 ms 388624 KB Output is correct
10 Correct 256 ms 386912 KB Output is correct
11 Correct 278 ms 387268 KB Output is correct
12 Correct 384 ms 388032 KB Output is correct
13 Correct 644 ms 393768 KB Output is correct
14 Correct 1284 ms 413412 KB Output is correct
15 Correct 827 ms 406212 KB Output is correct
16 Correct 810 ms 406388 KB Output is correct
17 Correct 325 ms 390564 KB Output is correct
18 Correct 351 ms 390644 KB Output is correct