Submission #382787

#	Time	Username	Problem	Language	Result	Execution time	Memory
382787		mehrdad_sohrabi	Jousting tournament (IOI12_tournament)	C++14	100 / 100	615 ms	56096 KiB

tournament

#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
 
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=2e5+100,M=20;
ll fen[MAXN];
ll par[MAXN][M];
void add(ll idx,ll val){
    for (;idx<MAXN;idx+= idx & (-idx)){
        fen[idx]+=val;
    }
}
ll getsum(ll idx){
    ll s=0;
    for (;idx;idx-= idx & (-idx)){
        s+=fen[idx];
    }
    return s;
}
ll getk(ll k){
    ll l=-1,r=MAXN-1;
    while(r-l>1){
        ll mid=(r+l)/2;
        if (getsum(mid)>=k) r=mid;
        else l=mid;
    }
    return r;
}
pii baze[MAXN];
vector <int> g[MAXN];
ll seg[MAXN*4];
void upd(ll nod,ll l,ll r,ll id,ll val){
    if (r-l==1){
        seg[nod]=val;
        return ;
    }
    ll mid=(r+l)/2;
    if (mid>id) upd(nod*2,l,mid,id,val);
    else upd(nod*2+1,mid,r,id,val);
    seg[nod]=max(seg[nod*2],seg[nod*2+1]);
}
ll get(ll nod,ll l,ll r,ll L,ll R){
    if (l>=R || L>=r) return 0;
    if (l>=L && r<=R) return seg[nod];
    ll mid=(r+l)/2;
    return max(get(nod*2+1,mid,r,L,R),get(nod*2,l,mid,L,R));
}
vector <pii> b;
pii baz[MAXN];
ll getpar(ll v,ll h){
    for (int i=0;i<M;i++){
        if ((h & (1<<i))) v=par[v][i];
    }
    return v;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    set <int> s;
    for (int i=1;i<=N;i++){
        s.insert(i);
        baze[i]={i,i};
        add(i,1);
    }
    for (int i=0;i<C;i++){
        S[i]++;
        E[i]++;
        ll l=getk(S[i]);
        ll r=getk(E[i]);
        baze[l].S=baze[r].S;
        b.pb({baze[l].F,baze[l].S});
        while(true){
            auto t=s.upper_bound(l);
            if (t==s.end()) break;
            if (*t>r) break;
            add(*t,-1);
            s.erase(t);
        }
    }
    sort(b.begin(),b.end());
  //  for (auto u : b){
    //    cout << u.F << " rth " << u.S << endl;
    //}
   // return 0;
    vector <pair <pii,int> > a;
    for (int i=1;i<=N;i++){
        a.pb({{i,-i},i});
        baz[i]={i,i};
    }
    for (int i=0;i<b.size();i++){
        a.pb({{b[i].F,-b[i].S},i+N+1});
        baz[i+N+1]=b[i];
    }
    a.pb({{0,-N*2},0});
    sort(a.begin(),a.end());
    vector <int> agh;
    agh.pb(0);
    for (int i=1;i<a.size();i++){
        //    cout << i << endl;
        while(-a[agh.back()].F.S<-a[i].F.S){
            agh.pop_back();
        }
        par[a[i].S][0]=a[agh.back()].S;
    //    cout << a[i].S << " " << a[i].F.F << " " << a[i].F.S << " " << par[a[i].S][0] << endl;
        agh.pb(i);
    }
   // return 0;
        for (int j=1;j<M;j++){
    for (int i=0;i<N*2;i++){
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }
    for (int i=1;i<N;i++){
        upd(1,1,N,i,K[i-1]);
    }
    ll mx=0,ans=0;
    for (int i=1;i<=N;i++){
        ll v=i;
        ll cnt=0;
        for (int i=M-1;i>-1;i--){
            ll u=par[v][i];
            if (u==0) continue;
            ll l=baz[u].F,r=baz[u].S;
            ll w=get(1,1,N,l,r);
            if (w<R){
            //cout << v << " " << u << " " << w << endl;
                v=u;
                cnt+=(1<<i);
            }
        }
        if (cnt>mx){
            ans=i-1;
            mx=cnt;
        }
    }
  //  cout << mx << endl;
    return ans;
}
/*
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;
 
}
 
5 3 3
1
0
2
4
1 3
0 1
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i=0;i<b.size();i++){
      |                  ~^~~~~~~~~
tournament.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=1;i<a.size();i++){
      |                  ~^~~~~~~~~

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