Submission #931295

#	Time	Username	Problem	Language	Result	Execution time	Memory
931295		kim	Jousting tournament (IOI12_tournament)	C++17	0 / 100	21 ms	13964 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define sz(x) (int)(x).size()
#define eb emplace_back

struct segment{
  int n;
  vector<int> t,lz;
  segment(int n_=0){init(n_);}
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    t.assign(n<<2,0);
    lz.assign(n<<2,0);
  }
  void flush(int i,int il,int ir){
    if(lz[i]){
      if(il!=ir) lz[i<<1]+=lz[i],lz[i<<1|1]+=lz[i];
      t[i]+=lz[i]*(ir-il+1);
      lz[i]=0;
    }
  }
  void upd(int i,int il,int ir,int l,int r,int x){
    flush(i,il,ir);
    if(l<=il&&ir<=r){
      lz[i]+=x;
      flush(i,il,ir);
      return;
    }
    if(il>r||ir<l) return;
    int mid=il+ir>>1;
    upd(i<<1,il,mid,l,r,x), upd(i<<1|1,mid+1,ir,l,r,x);
    t[i]=t[i<<1]+t[i<<1|1];
  }
  void upd(int l,int r,int x){upd(1,1,n,l,r,x);}
  int lower_bound(int i,int il,int ir,int x){
    flush(i,il,ir);
    if(t[i]<x) return ir+1;
    if(il==ir) return ir;
    int mid=il+ir>>1;
    flush(i<<1,il,mid);
    if(t[i<<1]<x) return lower_bound(i<<1|1,mid+1,ir,x-t[i<<1]);
    return lower_bound(i<<1,il,mid,x);
  }
  int lower_bound(int x){return lower_bound(1,1,n,x);}
}t;

struct RMQ{
  vector<vector<int>> a;
  void init(const vector<int> &b){
    int n=sz(b),m=32-__builtin_clz(n);
    a.assign(m,vector<int>(n));
    a[0]=b;
    for(int i=1;i<m;++i){
      for(int j=0;j+(1<<i)<=n;++j) a[i][j]=max(a[i-1][j],a[i-1][j+(1<<i-1)]);
    }
  }
  int qr(int l,int r){
    int i=31-__builtin_clz(r-l+1);
    return max(a[i][l],a[i][r-(1<<i)+1]);
  }
}rmq;

int qs[100005];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

  vector<pii> opr(C);
  t.init(N+5);
  t.upd(1,N,1);
  for(int i=0;i<C;++i){
    int l=t.lower_bound(S[i]+1), r=t.lower_bound(E[i]+1);
    opr[i]={l,r};
    if(l!=r) t.upd(l+1,r,-1);
    // cerr<<l<<"-"<<r<<endl;
  }
  vector<int> tmp(N);
  for(int i=1;i<N;++i) tmp[i]=K[i-1];
  rmq.init(tmp);
  for(auto &[l,r]:opr){
    if(rmq.qr(l,r-1)<R) ++qs[l-1],--qs[r];
  }
  int pos=0,mx=0;
  for(int i=0;i<N;++i){
    if(i>0) qs[i]+=qs[i-1];
    if(qs[i]>mx) mx=qs[i],pos=i;
  }
  return pos;

}

Compilation message (stderr)

tournament.cpp: In member function 'void segment::upd(int, int, int, int, int, int)':
tournament.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid=il+ir>>1;
      |             ~~^~~
tournament.cpp: In member function 'int segment::lower_bound(int, int, int, int)':
tournament.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid=il+ir>>1;
      |             ~~^~~
tournament.cpp: In member function 'void RMQ::init(const std::vector<int>&)':
tournament.cpp:56:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       for(int j=0;j+(1<<i)<=n;++j) a[i][j]=max(a[i-1][j],a[i-1][j+(1<<i-1)]);
      |                                                                       ~^~

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