Submission #799113

#	Time	Username	Problem	Language	Result	Execution time	Memory
799113		I_Love_EliskaM_	Jousting tournament (IOI12_tournament)	C++14	100 / 100	90 ms	17692 KiB

tournament

#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()
#define pi pair<int,int>
#define f first
#define s second
 
struct sgt {
  struct node {
    int x=0, cant=0, lazy=0;
  };
  vector<node> t; int sz=1;
  void push(int v) {
    if (t[v].cant) {
      t[2*v+1].cant=1;
      t[2*v+2].cant=1;
    }
    if (!t[2*v+1].cant) t[2*v+1].lazy+=t[v].lazy;
    if (!t[2*v+2].cant) t[2*v+2].lazy+=t[v].lazy;
    t[v].x+=t[v].lazy;
    t[v].lazy=0;
  }
  sgt(int n) {
    while (sz<n) sz<<=1;
    t.assign(4*sz,node());
  }
  void add(int v, int l, int r, int lx, int rx) {
    //if (t[v].cant) return;
    if (t[v].lazy) push(v);
    if (rx<=l || r<=lx) return;
    if (lx<=l && r<=rx) {
      if (t[v].cant) return;
      t[v].lazy++; 
      push(v);
      return;
    }
    int m=(l+r)>>1;
    add(2*v+1,l,m,lx,rx);
    add(2*v+2,m,r,lx,rx);
  }
  void add(int l, int r) {
    add(0,0,sz,l,r);
  }
  void set(int v, int l, int r, int lx, int rx) {
    //if (t[v].cant) return;
    if (t[v].lazy) push(v);
    if (rx<=l || r<=lx) return;
    if (lx<=l && r<=rx) {
      t[v].cant=1; return;
    }
    int m=(l+r)>>1;
    set(2*v+1,l,m,lx,rx);
    set(2*v+2,m,r,lx,rx);
  }
  void set(int l, int r) {
    set(0,0,sz,l,r);
  }
  void dfs(int v, int l, int r) {
    if (t[v].lazy) push(v);
    if (r-l==1) return;
    int m=(l+r)>>1;
    dfs(2*v+1,l,m);
    dfs(2*v+2,m,r);
  }
  void dfs() {
    dfs(0,0,sz);
  }
};

struct RMQ {
  vector<int> t; int sz=1;
  void build(int v, int l, int r) {
    if (r-l==1) return;
    int m=(l+r)>>1;
    build(2*v+1,l,m);
    build(2*v+2,m,r);
    t[v]=max(t[2*v+1],t[2*v+2]);
  }
  RMQ(vector<int>&a) {
    int n=a.size();
    while (sz<n) sz<<=1;
    t.assign(2*sz,0);
    forn(i,n) t[sz-1+i]=a[i];
    build(0,0,sz);
  } 
  int query(int v, int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) return t[v];
    int m=(l+r)>>1;
    int lq=query(2*v+1,l,m,lx,rx);
    int rq=query(2*v+2,m,r,lx,rx);
    return max(lq,rq);
  }
  int query(int l, int r) {
    return query(0,0,sz,l,r);
  }
};

const int sz=1<<20;
struct st {
  st *L, *R;
  int s;
  st() {
    L=R=NULL; s=0;
  }
  void add(int l, int r, int x) {
    ++s;
    if (r-l==1) return;
    int m=(l+r)>>1;
    if (x<m) {
      if (!L) L=new st();
      L->add(l,m,x);
    } else {
      if (!R) R=new st();
      R->add(m,r,x);
    }
  }
  void add(int x) {
    add(0,sz,x);
  }
  void del(int l, int r, int x) {
    --s;
    if (r-l==1) return;
    int m=(l+r)>>1;
    if (x<m) {
      L->del(l,m,x);
    } else {
      R->del(m,r,x);
    }
  }
  void del(int x) {
    del(0,sz,x);
  }
  int kth(int l, int r, int k) {
    if (r-l==1) return l;
    int m=(l+r)>>1;
    if (L) {
      if (L->s>=k) return L->kth(l,m,k);
      else return R->kth(m,r,k-L->s);
    } else {
      return R->kth(m,r,k);
    }
  }
  int kth(int k) {
    return kth(0,sz,k);
  }
}; 
 
st segs;

int GetBestPosition(int n, int c, int z, int*k, int*s, int*e) {
  
  vector<pi> q;
  forn(i,n) segs.add(i); segs.add(1e6);
  forn(i,c) {
    int l=s[i], r=e[i];
    int lq=segs.kth(l+1);
    int rq=segs.kth(r+2)-1;
    rq=min(rq,n-1);
    q.pb({lq,rq});
    for (int j=l+1; j<=r; ++j) {
      int x=segs.kth(l+2);
      segs.del(x);
    }
  }

  vector<int> a(n-1); forn(i,n-1) a[i]=k[i];
  sgt st(n);
  RMQ rmq(a);
  for(auto&x:q) {
    int l=x.f, r=x.s;
    int mx=rmq.query(l,r);
    if (mx<z) st.add(l,r+1);
    else st.set(l,r+1);
  }
  st.dfs();
  int ans=0, best=0;
  forn(i,n) {
    if (st.t[st.sz-1+i].x>ans) {
      ans=st.t[st.sz-1+i].x;
      best=i;
    }
  }
  return best;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    3 | #define forn(i,n) for(int i=0;i<n;++i)
      |                   ^~~
tournament.cpp:156:3: note: in expansion of macro 'forn'
  156 |   forn(i,n) segs.add(i); segs.add(1e6);
      |   ^~~~
tournament.cpp:156:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  156 |   forn(i,n) segs.add(i); segs.add(1e6);
      |                          ^~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51