Submission #931330

#	Time	Username	Problem	Language	Result	Execution time	Memory
931330		kim	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1037 ms	4196 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;

int lm[100005],rm[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);
    if(l!=r) t.upd(l+1,r,-1);
    opr[i]={l-1,r-1};
    // cerr<<l<<"-"<<r<<endl;
  }
  sort(opr.begin(),opr.end());

  for(int i=0,cur=-1;i<N-1;++i){
    if(K[i]>R) cur=i;
    lm[i]=cur;
  }
  for(int i=N-2,cur=N+1;i>=0;--i){
    if(K[i]>R) cur=i;
    rm[i]=cur;
  }

  int ans=0,mx=0;
  for(int i=0;i<N;++i){
    int cnt=0;
    for(auto &[l,r]:opr){
      if(l>i||r<i||rm[l]<r) continue;
      ++cnt;
    }
    if(cnt>mx) mx=cnt,ans=i;
  }
  return ans;

}

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;
      |             ~~^~~

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