| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 155935 | junodeveloper | 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 sz(x) (int)x.size()
using namespace std;
const int maxn=500000;
const int tmax=20*maxn+4*maxn;
int n,m;
int root[maxn+10];
int tree[tmax],tl[tmax],tr[tmax],tcnt;
vector<int> vx,vy;
int build(int s,int e) {
int u=++tcnt;
tree[u]=0;
if(s==e) return u;
int mid=(s+e)/2;
tl[u]=build(s,mid);
tr[u]=build(mid+1,e);
return u;
}
int update(int u,int s,int e,int p,int x) {
if(p<s||e<p) return u;
int nu=++tcnt;
tree[nu]=tree[u]+x;
if(s==e) return nu;
int mid=(s+e)/2;
tl[nu]=update(tl[u],s,mid,p,x);
tr[nu]=update(tr[u],mid+1,e,p,x);
return nu;
}
int query(int u,int s,int e,int l,int r) {
if(l>r) return 0;
if(e<l||r<s) return 0;
if(l<=s&&e<=r) return tree[u];
int mid=(s+e)/2;
return query(tl[u],s,mid,l,r)+query(tr[u],mid+1,e,l,r);
}
void init(int N, int A[], int B[]) {
n=N;
vector<int> a;
int i,j;
for(i=0;i<n;i++)a.push_back(i);
sort(a.begin(),a.end(),[&](int x,int y) {
return B[x]<B[y];
});
for(i=0;i<n;i++) {
vx.push_back(A[a[i]]);
vy.push_back(B[a[i]]);
}
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
root[n]=build(0,sz(vx)-1);
for(i=n-1;i>=0;i--) {
j=lower_bound(vx.begin(),vx.end(),A[a[i]])-vx.begin();
root[i]=update(root[i+1],0,sz(vx)-1,j,1);
}
}
int can(int M, int K[]) {
m=M;
int i,j,k;
sort(K,K+m);
long long mx=-1e18,q1,q2,cur=0;
for(i=0;i<m;i++) {
j=lower_bound(vy.begin(),vy.end(),K[i])-vy.begin();
k=lower_bound(vx.begin(),vx.end(),K[i]+1)-vx.begin()-1;
q1=query(root[j],0,sz(vx)-1,0,k);
if(i) {
k=lower_bound(vx.begin(),vx.end(),K[i-1]+1)-vx.begin()-1;
q2=query(root[j],0,sz(vx)-1,0,k);
} else q2=0;
cur=K[i]-q1+max(0ll,cur+q2);
mx=max(mx,cur);
}
return mx<=0;
}
int main() {
const int N=4;
int A[N]={1,2,2,2};
int B[N]={2,3,3,4};
init(N,A,B);
const int M=2;
int K[M]={1,1};
printf("%d",can(M,K));
return 0;
}