Submission #795640

#	Time	Username	Problem	Language	Result	Execution time	Memory
795640		I_Love_EliskaM_	Teams (IOI15_teams)	C++14	34 / 100	4083 ms	416036 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second

const int sz=1<<20;
struct sgt {
  sgt *L, *R;
  int s;
  sgt() {
    L=R=NULL; s=0;
  }
  sgt* add(int l, int r, int i, int x) {
    if (r-l==1) {
      sgt* nw = new sgt();
      nw->s = s+x;
      return nw;
    }
    int m=(l+r)>>1;
    if (i<m) {
      if (!L) L=new sgt();
      sgt* newleft = L->add(l,m,i,x);
      sgt* nw = new sgt();
      nw->L = newleft;
      nw->R = R;
      nw->s = s+x;
      return nw;
    } else {
      if (!R) R=new sgt();
      sgt* newright = R->add(m,r,i,x);
      sgt* nw = new sgt();
      nw->L = L;
      nw->R = newright;
      nw->s = s+x;
      return nw;
    }
  }
  sgt* add(int i, int x) {
    return add(0,sz,i,x);
  }

  int sum(int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) return s;
    int m=(l+r)>>1;
    int lq = L?L->sum(l,m,lx,rx):0;
    int rq = R?R->sum(m,r,lx,rx):0;
    return lq+rq;
  }
  int sum(int l, int r) {
    return sum(0,sz,l,r);
  }
  int get(int i) {
    return sum(0,sz,0,i+1);
  }
};
sgt* st[(int)5e5+55];

pi a[(int)5e5];
int n;

void init(int _n, int f[], int s[]) {
  n=_n;
  forn(i,n) a[i]={f[i],s[i]};
  vector<vector<int>> v(n+1);
  forn(i,n) v[a[i].s].pb(i);
  st[0]=new sgt();
  forn(i,n) {
    st[i+1]=st[i];
    for(auto&x:v[i+1]) {
      auto t=st[i+1]->add(a[x].f,1);
      st[i+1]=t;
    }
  }
}

int can(int m, int k[]) {
  vector<int> v(m);
  forn(i,m) v[i]=k[i];
  sort(all(v));
  int s=0; forn(i,m) s+=k[i];
  if (s>n) return 0;
  
  if (m>=500) {
    reverse(all(v));
    set<pi> q;
    vector<vector<int>> add(n+1);
    vector<vector<int>> del(n+1);
    forn(i,n) add[a[i].s].pb(i), del[a[i].f].pb(i);
    int p=0;
    for (int i=n; i>0; --i) {
      for (auto&x:add[i]) {
        q.insert({-a[x].f,x});
      }
      while (p<m && i==v[p]) {
        if (q.size()<i) return 0;
        forn(iter,i) {
          auto it=q.begin(); q.erase(q.begin());
        }
        ++p;
      }
      for (auto&x:del[i]) {
        if (q.count({-a[x].f,x})) q.erase({-a[x].f,x});
      }
    }
    return p==m;
  }

  vector<int> dp(m+1,-1e9);
  dp[0]=0;
  forn(i,m) {
    forn(j,i+1) {
      int cnt;
      if (j==0) {
        cnt=st[n]->sum(0,v[i]+1) - st[v[i]-1]->sum(0,v[i]+1);
      } else {
        cnt=st[n]->sum(v[j-1]+1,v[i]+1) - st[v[i]-1]->sum(v[j-1]+1,v[i]+1);
      }
      dp[i+1]=max(dp[i+1],dp[j]+v[i]-cnt);
    }
    if (dp[i+1]>0) return 0;
  }
  return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:102:21: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         if (q.size()<i) return 0;
      |             ~~~~~~~~^~
teams.cpp:104:16: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  104 |           auto it=q.begin(); q.erase(q.begin());
      |                ^~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23