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 ll int
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,l;
ll tree[1500005],lef[1500005],righ[1500005];
ll root[500005],k[500005],dp[500005];
ll snode,prevroot,tim;
set <ll> st1;
set < pair <ll,ll> > st;
vector <ll> v[500005];
void build(ll node,ll le,ll ri) {
if(le==ri) {
tree[node]=0;
return;
}
snode++;
lef[node]=snode;
build(snode,le,(le+ri)/2);
snode++;
righ[node]=snode;
build(snode,(le+ri)/2+1,ri);
tree[node]=tree[lef[node]]+tree[righ[node]];
}
void update(ll node,ll prevnode,ll le,ll ri,ll idx) {
if(ri<idx || le>idx) return;
if(le==ri) {
tree[node]=tree[prevnode]+1;
return;
}
if(idx<=(le+ri)/2) {
snode++; lef[node]=snode; righ[node]=righ[prevnode];
update(snode,lef[prevnode],le,(le+ri)/2,idx);
} else {
snode++; righ[node]=snode; lef[node]=lef[prevnode];
update(snode,righ[prevnode],(le+ri)/2+1,ri,idx);
}
tree[node]=tree[lef[node]]+tree[righ[node]];
}
ll getans(ll node,ll le,ll ri,ll start,ll end) {
if(ri<start || le>end) return 0;
if(start<=le && ri<=end) return tree[node];
return getans(lef[node],le,(le+ri)/2,start,end)+getans(righ[node],(le+ri)/2+1,ri,start,end);
}
ll Z(ll x,ll y) {
return getans(root[y],y,n,1,n)-getans(root[x],y,n,1,n);
}
void init(int N, int A[], int B[]) {
n=N;
for(ll i=0;i<N;i++) {
v[A[i]].pb(B[i]);
}
snode=1;
root[0]=snode;
build(1,1,n);
for(ll i=1;i<=N;i++) {
prevroot=root[i-1];
root[i]=root[i-1];
for(ll j=0;j<v[i].size();j++) {
snode++;
root[i]=snode;
update(root[i],prevroot,1,n,v[i][j]);
prevroot=root[i];
}
}
}
ll go(ll x,ll y) {
ll le=k[b]+1;
ll ri=n;
ll ans=0;
while(le<=ri) {
int mid=(le+ri)/2;
if(dp[a]-dp[b]<-(getans(root[k[b]],mid,n,1,n)-getans(root[k[a]],mid,n,1,n))) {
ans=mid; ri=mid-1;
} else le=mid+1;
}
return ans;
}
void add(ll x) {
if(!st1.size()) { st1.insert(x); return; }
ll pat=*(--st1.end());
st1.insert(x);
tim=go(pat,x);
if(tim) st.insert({tim,x});
}
void del(ll x) {
if(!st1.count(x)) return;
st1.erase(x);
if(!st1.size()) return;
ll pat=-1;
ll did=-1;
if(*st1.begin()<x) pat=*(--st1.upper_bound(x));
if(st1.upper_bound(x)==st1.end()) did=*st1.upper_bound(x);
if(did!=-1) {
tim=go(x,did);
if(tim) st.erase({tim,did});
}
if(pat!=-1) {
tim=go(pat,x);
if(tim) st.erase({tim,x});
}
if(did!=-1 && pat!=-1) {
tim=go(pat,did);
if(tim) st.insert({tim,did});
}
}
int can(int M, int K[]) {
m=M;
for(ll i=m;i>=1;i--) {
K[i]=K[i-1];
}
int sum=0;
for(ll i=1;i<=m;i++) {
sum+=k[i];
}
if(sum>=n) return 0;
sort(k+1,k+1+m);
dp[0]=0;
add(0);
for(ll i=1;i<=m;i++) {
while(st.size()) {
set < pair <ll,ll> >::iterator it;
it=st.begin();
if((*it).f<=k[i]) del((*it).sc);
else break;
}
int idx=*(--st1.end());
dp[i]=dp[idx]+Z(k[idx],k[i])-k[i];
if(dp[i]<0) return 0;
add(i);
}
return 1;
}
Compilation message (stderr)
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:54:12: warning: declaration of 'i' shadows a global declaration [-Wshadow]
54 | for(ll i=0;i<N;i++) {
| ^
teams.cpp:8:12: note: shadowed declaration is here
8 | ll a,b,c,d,i,e,f,g,n,m,l;
| ^
teams.cpp:60:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
60 | for(ll i=1;i<=N;i++) {
| ^
teams.cpp:8:12: note: shadowed declaration is here
8 | ll a,b,c,d,i,e,f,g,n,m,l;
| ^
teams.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(ll j=0;j<v[i].size();j++) {
| ~^~~~~~~~~~~~
teams.cpp: In function 'int go(int, int)':
teams.cpp:71:10: warning: unused parameter 'x' [-Wunused-parameter]
71 | ll go(ll x,ll y) {
| ^
teams.cpp:71:15: warning: unused parameter 'y' [-Wunused-parameter]
71 | ll go(ll x,ll y) {
| ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:113:12: warning: declaration of 'i' shadows a global declaration [-Wshadow]
113 | for(ll i=m;i>=1;i--) {
| ^
teams.cpp:8:12: note: shadowed declaration is here
8 | ll a,b,c,d,i,e,f,g,n,m,l;
| ^
teams.cpp:117:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
117 | for(ll i=1;i<=m;i++) {
| ^
teams.cpp:8:12: note: shadowed declaration is here
8 | ll a,b,c,d,i,e,f,g,n,m,l;
| ^
teams.cpp:124:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
124 | for(ll i=1;i<=m;i++) {
| ^
teams.cpp:8:12: note: shadowed declaration is here
8 | ll a,b,c,d,i,e,f,g,n,m,l;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |