Submission #416177

#	Time	Username	Problem	Language	Result	Execution time	Memory
416177		Theo830	Jousting tournament (IOI12_tournament)	C++17	100 / 100	131 ms	12080 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

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

int main() {
  int tmp;
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
*/
ll pre[100005] = {0};
ll sum(ll l,ll r){
    return pre[r+1] - pre[l];
}
struct node{
    ll sum = 0,lazy = 0;
};
node seg[400005],seg2[400005];
void build(ll s,ll e,ll idx){
    if(s == e){
        seg[idx].sum = 1;
        return;
    }
    ll mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}
void update(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        seg[idx].lazy = 1;
        seg[idx].sum = 0;
        return;
    }
    else if(s > qe || e < qs){
        return;
    }
    if(seg[idx].lazy == 1){
        seg[idx].lazy = 0;
        seg[idx*2].sum = seg[idx*2+1].sum = 0;
        seg[idx*2].lazy = seg[idx*2+1].lazy = 1;
    }
    ll mid = (s+e)/2;
    update(s,mid,qs,qe,idx*2);
    update(mid+1,e,qs,qe,idx*2+1);
    seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}
void upd(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        seg2[idx].lazy++;
        seg2[idx].sum += (e - s + 1);
        return;
    }
    else if(s > qe || e < qs){
        return;
    }
    ll mid = (s+e)/2;
    seg2[idx*2].sum += seg2[idx].lazy * (mid - s + 1);
    seg2[idx*2+1].sum += seg2[idx].lazy * (e - mid);
    seg2[idx*2].lazy += seg2[idx].lazy;
    seg2[idx*2+1].lazy += seg2[idx].lazy;
    seg2[idx].lazy = 0;
    upd(s,mid,qs,qe,idx*2);
    upd(mid+1,e,qs,qe,idx*2+1);
    seg2[idx].sum = seg2[idx*2].sum + seg2[idx*2+1].sum;
}
ll ask(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        return seg2[idx].sum;
    }
    else if(s > qe || e < qs){
        return 0;
    }
    ll mid = (s+e)/2;
    seg2[idx*2].sum += seg2[idx].lazy * (mid - s + 1);
    seg2[idx*2+1].sum += seg2[idx].lazy * (e - mid);
    seg2[idx*2].lazy += seg2[idx].lazy;
    seg2[idx*2+1].lazy += seg2[idx].lazy;
    seg2[idx].lazy = 0;
    ll a = ask(s,mid,qs,qe,idx*2);
    ll b = ask(mid+1,e,qs,qe,idx*2+1);
    return a + b;
}
ll query(ll s,ll e,ll k,ll idx){
    if(s == e){
        return s-1;
    }
    if(seg[idx].lazy == 1){
        seg[idx].lazy = 0;
        seg[idx*2].sum = seg[idx*2+1].sum = 0;
        seg[idx*2].lazy = seg[idx*2+1].lazy = 1;
    }
    ll mid = (s+e)/2;
    if(seg[idx*2].sum >= k){
        return query(s,mid,k,idx*2);
    }
    else{
        return query(mid+1,e,k - seg[idx*2].sum,idx*2+1);
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    ll posa = 0;
    ll ans = 0;
    f(i,0,N-1){
        pre[i+1] = pre[i] + (K[i] > R);
    }
    ll n = N+1;
    build(1,n,1);
    f(i,0,C){
        S[i] = query(1,n,S[i]+1,1);
        E[i] = query(1,n,E[i]+2,1) - 1;
        update(1,n,S[i]+2,E[i]+1,1);
    }
    f(j,0,C){
        if(sum(S[j],E[j]-1) == 0){
            upd(1,n,S[j]+1,E[j]+1,1);
        }
    }
    f(i,0,n){
        ll res = ask(1,n,i+1,i+1,1);
        if(res > posa){
            posa = res;
            ans = i;
        }
    }
    return ans;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/

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