Submission #542112

#TimeUsernameProblemLanguageResultExecution timeMemory
542112wildturtleTeams (IOI15_teams)C++17
0 / 100
162 ms86460 KiB
#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 start,ll end,ll le,ll ri) { 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); } 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[]) { st.clear(); st1.clear(); m=M; for(ll i=m;i>=1;i--) { k[i]=K[i-1]; dp[i]=0; } 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++) dp[i]=1e9; for(ll i=1;i<=m;i++) { while(st.size()) { multiset < pair <ll,ll> > :: iterator 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; } 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]; } } }

Compilation message (stderr)

teams.cpp: In function 'int go(int, int)':
teams.cpp:52:10: warning: unused parameter 'x' [-Wunused-parameter]
   52 | ll go(ll x,ll y) {
      |          ^
teams.cpp:52:15: warning: unused parameter 'y' [-Wunused-parameter]
   52 | ll go(ll x,ll y) {
      |               ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:96:12: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   96 |     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:101:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  101 |  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:108:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  108 |  for(ll i=1;i<=m;i++) dp[i]=1e9;
      |         ^
teams.cpp:8:12: note: shadowed declaration is here
    8 | ll a,b,c,d,i,e,f,g,n,m,l;
      |            ^
teams.cpp:109:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  109 |  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: In function 'void init(int, int*, int*)':
teams.cpp:124:12: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  124 |     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:130:9: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  130 |  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:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(ll j=0;j<v[i].size();j++) {
      |                    ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...