| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 537911 | new_acc | Teams (IOI15_teams) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,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]);
}
}
bool can(int m,int v[]){
sort(v,v+m);
for(int i=0;i<m;i++) w[i+1]=v[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,bool> >act;
ok[1]=1;
curr.insert(1),act.insert({2,0});
while(1){
auto it2=act.begin();
pair<int,bool> v=*it2;
act.erase(it2);
if(v.fi>m) break;
if(v.se){
if(!ok[v.fi]) continue;
ok[v.fi]=0;
auto it=curr.lower_bound(v.fi);
it--;
int mn=*it;
it++,it++;
if(it!=curr.end()){
int wi=*it;
curr.erase(it);
act.insert({bs2(mn,wi,v.fi+1,m),1});
}
}else{
auto it=curr.end();
it--;
dp[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),1});
act.insert({v.fi+1,0});
}
}
for(int i=1;i<=m;i++) if(dp[i]<0) return 0;
return 1;
}
/*int main(){
vi a,b;
int n;
cin>>n;
for(int i=1,x,d;i<=n;i++){
cin>>x>>d;
a.push_back(x),b.push_back(d);
}
init(n,a,b);
int m;
cin>>m;
vi pom;
for(int i=1,x;i<=m;i++){
cin>>x;
pom.push_back(x);
}
cout<<can(m,pom)<<"\n";
}*/