Submission #1246969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246969		Malix	Jousting tournament (IOI12_tournament)	C++20	100 / 100	104 ms	17992 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;

#define REP(a,b,c) for(int a=b;a<c;a++)
#define S second
#define F first
#define LSOne(s) ((s)&(-s))
#define PB push_back
#define all(x) (x).begin(),(x).end()

vi ft;
int n;

void update(int x,int v){
  x++;
  while(x<=n){
    ft[x]+=v;
    x+=LSOne(x);
  }
}

int query(int x){
  x++;
  int ans=0;
  while(x){
    ans+=ft[x];
    x-=LSOne(x);
  }
  return ans;
}

int solve(int x){
  int l=0,r=n-1;
  while(l!=r){
    int m=(l+r)/2;
    if(query(m)>=x+1)r=m;
    else l=m+1;
  }
  return l;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  n=N;
  ft.resize(n+1,0);
  REP(i,0,n)update(i,1);
  vector<pi> a(n),b;
  REP(i,0,n)a[i]={i,i};
  set<int> st;
  REP(i,0,n)st.insert(i);
  int k=log2(n-1)+1;
  vii mx(n-1,vi(k,0));
  REP(i,0,n-1)mx[i][0]=K[i];
  REP(j,1,k)REP(i,0,n-1)if(i+(1<<(j-1))<n-1)mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
  REP(i,0,C){
    int x=solve(S[i]),y=solve(E[i]);
    x=a[x].F;y=a[y].S;
    a[y]={x,y};
    int z=y-x,lg=log2(z);
    if(max(mx[x][lg],mx[y-(1<<lg)][lg])<R)b.PB({x,y});
    auto it=st.lower_bound(x);
    while(it!=st.end()&&*it<y){
      update(*it,-1);
      st.erase(it);
      it=st.lower_bound(x);
    }
  }
  sort(all(b));
  vi ans(n,0);
  int pos=0,cnt=0,sz=b.size();
  priority_queue<int,vi,greater<int>> pq;
  REP(i,0,n){
    while(pos<sz&&b[pos].F<=i){
      pq.push(b[pos].S);
      pos++;cnt++;
    }
    while(!pq.empty()&&pq.top()<i){
      pq.pop();
      cnt--;
    }
    ans[i]=cnt;
  }
  int ps=0;
  REP(i,0,n)if(ans[i]>ans[ps])ps=i;
  return ps;
}

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