oj.uz

Submission #537933

# Submission time Handle Problem Language Result Execution time Memory
537933 2022-03-15T22:18:09 Z new_acc Teams (IOI15_teams) C++14
100 / 100
 2415 ms 380372 KB 
#include "teams.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
struct item{
	item *l,*r;
	int val;
};
pitem wsk[N];
pair<int,int>t[N];
bitset<N>ok;
int n,dp[N],w[N];
void upd(int ind,pitem v,pitem nv,int p=0,int k=SS-1){
	nv->val=v->val+1;
	if(!(v->r)){
		nv->r=nullptr,nv->l=nullptr;
		return;
	}
	if(ind<=(p+k)>>1){
		nv->r=v->r,nv->l=new item;
		upd(ind,v->l,nv->l,p,(p+k)>>1);
	}else{
		nv->l=v->l,nv->r=new item;
		upd(ind,v->r,nv->r,((p+k)>>1)+1,k);
	}
}
void build(pitem v,int akt){
	if(!v) return;
	v->val=0;
	if(akt>SS) v->l=nullptr,v->r=nullptr;
	else{
		v->r=new item,v->l=new item;
		build(v->r,(akt<<1)+1),build(v->l,(akt<<1));
	}
}
int Query(pitem v,int a,int b,int p=0,int k=SS-1){
	if(p>b or k<a) return 0;
	if(p>=a and k<=b) return v->val;
	else return Query(v->l,a,b,p,(p+k)>>1)+Query(v->r,a,b,((p+k)>>1)+1,k);
}
int bs(int x){
	int pocz=1,kon=n,res=0,sr;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		if(t[sr].fi<=x) res=sr,pocz=sr+1;
		else kon=sr-1;
	}
	return res;
}
int sq(int a,int b){
	return Query(wsk[bs(a)],b,SS-1);
}
int bs2(int i,int j,int pocz,int kon){
	int sr,res=kon+1;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		int val1=sq(w[sr],w[sr])-sq(w[i],w[sr])+dp[i]-w[sr];
		int val2=sq(w[sr],w[sr])-sq(w[j],w[sr])+dp[j]-w[sr];
		if(val1<=val2) kon=sr-1,res=sr;
		else pocz=sr+1;
	}
	return res;
}
void init(int nn,int a[],int b[]){
	n=nn;
	for(int i=0;i<n;i++) t[i+1]={a[i],b[i]};
	sort(t+1,t+1+n);
	wsk[0]=new item;
	build(wsk[0],1);
	for(int i=1;i<=n;i++){
		wsk[i]=new item;
		upd(t[i].se,wsk[i-1],wsk[i]);
	}
}
int can(int m,int vv[]){
	sort(vv,vv+m);
	for(int i=0;i<m;i++) w[i+1]=vv[i];
	dp[1]=sq(w[1],w[1])-w[1];
	if(m==1) return dp[1]>=0;
	for(int i=1;i<=m;i++) ok[i]=0;
	set<int> curr;
	set<pair<int,int> >act;
	ok[1]=1;
	curr.insert(1),act.insert({2,0});
	while(1){
		auto it2=act.begin();
		pair<int,int> v=*it2;
		act.erase(it2);
		if(v.fi>m) break;
		if(v.se<0){	
			v.se*=-1;
			if(!ok[v.se]) continue;
			ok[v.se]=0;
			auto it=curr.lower_bound(v.se);
			it--;			
			int mn=*it;
			it++,it++;
			if(it!=curr.end()){
				int wi=*it;
				act.insert({bs2(mn,wi,v.se+1,m),-wi});
			}
			it--;
			curr.erase(it);
		}else{
			auto it=curr.end();
			it--;
			dp[v.fi]=min(sq(w[v.fi],w[v.fi])-w[v.fi],sq(w[v.fi],w[v.fi])-sq(w[*it],w[v.fi])+dp[*it]-w[v.fi]);
			curr.insert(v.fi);
			it=curr.end();
			it--,it--;
			act.insert({bs2(*it,v.fi,v.fi+1,m),-(v.fi)});
			act.insert({v.fi+1,0});
			ok[v.fi]=1;
		}
	}
	for(int i=1;i<=m;i++) if(dp[i]<0) return 0;
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 33104 KB Output is correct
2 Correct 40 ms 33060 KB Output is correct
3 Correct 41 ms 33228 KB Output is correct
4 Correct 41 ms 33176 KB Output is correct
5 Correct 42 ms 33140 KB Output is correct
6 Correct 89 ms 34224 KB Output is correct
7 Correct 39 ms 33220 KB Output is correct
8 Correct 38 ms 33156 KB Output is correct
9 Correct 41 ms 33136 KB Output is correct
10 Correct 40 ms 33172 KB Output is correct
11 Correct 36 ms 33124 KB Output is correct
12 Correct 47 ms 33156 KB Output is correct
13 Correct 42 ms 33192 KB Output is correct
14 Correct 39 ms 33200 KB Output is correct
15 Correct 37 ms 33100 KB Output is correct
16 Correct 47 ms 33180 KB Output is correct
17 Correct 38 ms 33160 KB Output is correct
18 Correct 41 ms 33108 KB Output is correct
19 Correct 38 ms 33124 KB Output is correct
20 Correct 41 ms 33164 KB Output is correct
21 Correct 38 ms 33156 KB Output is correct
22 Correct 38 ms 33096 KB Output is correct
23 Correct 36 ms 33088 KB Output is correct
24 Correct 37 ms 33100 KB Output is correct
25 Correct 40 ms 33080 KB Output is correct
26 Correct 45 ms 33132 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 98288 KB Output is correct
2 Correct 153 ms 98252 KB Output is correct
3 Correct 177 ms 98268 KB Output is correct
4 Correct 849 ms 108808 KB Output is correct
5 Correct 121 ms 98252 KB Output is correct
6 Correct 122 ms 98204 KB Output is correct
7 Correct 123 ms 98228 KB Output is correct
8 Correct 128 ms 98892 KB Output is correct
9 Correct 366 ms 102428 KB Output is correct
10 Correct 206 ms 100520 KB Output is correct
11 Correct 134 ms 98884 KB Output is correct
12 Correct 130 ms 98792 KB Output is correct
13 Correct 129 ms 99080 KB Output is correct
14 Correct 138 ms 99108 KB Output is correct
15 Correct 141 ms 99208 KB Output is correct
16 Correct 146 ms 99204 KB Output is correct
17 Correct 126 ms 99172 KB Output is correct
18 Correct 121 ms 99128 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 98708 KB Output is correct
2 Correct 506 ms 98720 KB Output is correct
3 Correct 277 ms 101708 KB Output is correct
4 Correct 879 ms 109028 KB Output is correct
5 Correct 467 ms 98604 KB Output is correct
6 Correct 473 ms 98676 KB Output is correct
7 Correct 501 ms 98704 KB Output is correct
8 Correct 490 ms 99764 KB Output is correct
9 Correct 295 ms 102392 KB Output is correct
10 Correct 604 ms 101040 KB Output is correct
11 Correct 542 ms 99560 KB Output is correct
12 Correct 487 ms 99660 KB Output is correct
13 Correct 424 ms 99960 KB Output is correct
14 Correct 345 ms 101420 KB Output is correct
15 Correct 371 ms 100144 KB Output is correct
16 Correct 386 ms 100056 KB Output is correct
17 Correct 377 ms 99960 KB Output is correct
18 Correct 456 ms 99968 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1705 ms 358928 KB Output is correct
2 Correct 1570 ms 359096 KB Output is correct
3 Correct 1108 ms 364628 KB Output is correct
4 Correct 2415 ms 379100 KB Output is correct
5 Correct 1380 ms 358808 KB Output is correct
6 Correct 1369 ms 358860 KB Output is correct
7 Correct 1454 ms 358812 KB Output is correct
8 Correct 1406 ms 363468 KB Output is correct
9 Correct 1546 ms 380372 KB Output is correct
10 Correct 1527 ms 363784 KB Output is correct
11 Correct 1302 ms 362620 KB Output is correct
12 Correct 1225 ms 363316 KB Output is correct
13 Correct 1538 ms 365208 KB Output is correct
14 Correct 1195 ms 369716 KB Output is correct
15 Correct 1161 ms 366048 KB Output is correct
16 Correct 1139 ms 366128 KB Output is correct
17 Correct 1167 ms 365596 KB Output is correct
18 Correct 1148 ms 365352 KB Output is correct