| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1099129 | alexander_707070 | Scales (IOI15_scales) | 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<bits/stdc++.h>
//#include "teams.h"
#define MAXN 1000007
using namespace std;
int n,m;
pair<int,int> p[MAXN];
int k[MAXN];
struct interval{
int l,r,k,e;
int len(){
return r-l+1;
}
};
interval combine(interval a,interval b){
interval c={a.l,b.r,0,0};
if(a.k>a.len())swap(a,b);
if(a.k>a.len() and b.k>b.len()){
c.k=c.len()+1;
c.e=0;
}else if(b.k>b.len()){
c.k=a.k+b.len();
c.e=a.e;
}else{
if(a.e>b.e)swap(a,b);
c.e=a.e;
c.k=a.k+b.k-1;
}
return c;
}
struct PST{
struct node{
int l,r,sum;
};
node tree[MAXN*60];
int root[MAXN],num,last;
void upgrade(){
last++; root[last]=num;
}
void addnode(int l,int r){
num++;
tree[num].l=l; tree[num].r=r;
}
int update(int v,int l,int r,int pos){
if(l==r){
addnode(0,0);
tree[num].sum=tree[v].sum+1;
return num;
}else{
int tt=(l+r)/2;
int lt=tree[v].l,rt=tree[v].r;
if(pos<=tt){
lt=update(tree[v].l,l,tt,pos);
}else{
rt=update(tree[v].r,tt+1,r,pos);
}
addnode(lt,rt);
tree[num].sum=tree[lt].sum+tree[rt].sum;
return num;
}
}
int getkth(int v1,int v2,int l,int r,int k){
if(l==r)return l;
int tt=(l+r)/2;
if(tree[tree[v2].l].sum-tree[tree[v1].l].sum>=k)return getkth(tree[v1].l,tree[v2].l,l,tt,k);
return getkth(tree[v1].r,tree[v2].r,tt+1,r,k-(tree[tree[v2].l].sum-tree[tree[v1].l].sum));
}
void upd(int x){
update(root[last],1,n,x);
upgrade();
}
int kth(int l,int r,int k){
return getkth(root[l-1],root[r],1,n,k);
}
int smallest(int l,int r,int val){
int from=0,to=r-l+2,tt;
while(from+1<to){
tt=(from+to)/2;
if(kth(l,r,tt)>=val){
to=tt;
}else{
from=tt;
}
}
return to;
}
}seg;
//void init(int N, int A[], int B[]) {
void init(int N, vector<int> A, vector<int> B) {
n=N;
for(int i=1;i<=n;i++){
p[i]={A[i-1],B[i-1]};
}
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)seg.upd(p[i].second);
}
int findpos(int from,int val){
int l=from,r=n+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(p[tt].first<=val){
l=tt;
}else{
r=tt;
}
}
return l;
}
//int can(int M,int K[]) {
int can(int M,vector<int> K) {
m=M;
for(int i=1;i<=m;i++){
k[i]=K[i-1];
}
sort(k+1,k+m+1);
vector<interval> w;
int pt=0;
for(int i=1;i<=m;i++){
int nxt=findpos(pt,k[i]);
if(nxt>pt){
w.push_back({pt+1,nxt,1,seg.kth(pt+1,nxt,1)});
pt=nxt;
}
for(int f=int(w.size())-1;f>=0;f--){
int s=seg.smallest(w[f].l,w[f].r,k[i]);
if(s<w[f].k)break;
w[f].k=s;
if(s<=w[f].len())w[f].e=seg.kth(w[f].l,w[f].r,s);
else w[f].e=0;
}
if(w.empty())return 0;
while(k[i]>0){
if(w.size()==1){
if(w[0].k+k[i]-1>w[0].len())return 0;
w[0].k+=k[i];
break;
}
interval s=w.back();
for(int z=20;z>=0;z--){
if((1<<z)>s.len()-s.k+1 or (1<<z)>k[i])continue;
int curr=seg.kth(s.l,s.r,s.k+(1<<z)-1);
if(curr<w[w.size()-2].e){
k[i]-=(1<<z);
s.k+=(1<<z);
}
}
if(s.k<=s.len())s.e=seg.kth(s.l,s.r,s.k);
else s.e=0;
w[w.size()-1]=s;
if(k[i]>0){
w[w.size()-2]=combine(w[w.size()-2],w[w.size()-1]);
w.pop_back();
}
}
}
return 1;
}
int main(){
init(5,{4,3,2,2,1},{4,5,3,5,4});
cout<<can(2,{1,2})<<"\n";
return 0;
}
/*
4 4
3 5
2 3
2 5
1 4
5
*/