Submission #851728

#	Time	Username	Problem	Language	Result	Execution time	Memory
851728		abcvuitunggio	Jousting tournament (IOI12_tournament)	C++17	100 / 100	99 ms	10592 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
int n,st[400001][2],lazy[400001][2],l[100001],r[100001],f[100001];
vector <pair <int, int>> ve;
void down(int node, int l, int r, int i){
    if (!lazy[node][i]||l==r)
        return;
    st[node<<1][i]=st[node<<1|1][i]=0;
    lazy[node<<1][i]=lazy[node<<1|1][i]=1;
    lazy[node][i]=0;
}
void build(int node, int l, int r){
    st[node][0]=st[node][1]=r-l+1;
    if (l==r)
        return;
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
}
void update(int node, int l, int r, int u, int v, int i){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        st[node][i]=0;
        lazy[node][i]=1;
        return;
    }
    down(node,l,r,i);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,i);
    update(node<<1|1,mid+1,r,u,v,i);
    st[node][i]=st[node<<1][i]+st[node<<1|1][i];
}
int get(int node, int l, int r, int val, int i){
    if (l==r)
        return l;
    down(node,l,r,i);
    int mid=(l+r)>>1;
    return (st[node<<1][i]<val?get(node<<1|1,mid+1,r,val-st[node<<1][i],i):get(node<<1,l,mid,val,i));
}
void update(int i, int val){
    i++;
    for (;i<=n;i+=i&(-i))
        f[i]+=val;
}
int get(int i){
    int res=0;
    i++;
    for (;i;i-=i&(-i))
        res+=f[i];
    return res;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    n=N;
    build(1,0,N-1);
    for (int i=0;i<C;i++){
        S[i]=get(1,0,N-1,S[i]+1,0);
        E[i]=get(1,0,N-1,E[i]+1,1);
        update(1,0,N-1,S[i]+1,E[i],0);
        update(1,0,N-1,S[i],E[i]-1,1);
        ve.emplace_back(S[i],E[i]);
    }
    sort(ve.begin(),ve.end());
    l[0]=0;
    r[N-1]=N-1;
    for (int i=0;i<N-1;i++)
        l[i+1]=(K[i]>R?i+1:l[i]);
    for (int i=N-2;i>=0;i--)
        r[i]=(K[i]>R?i:r[i+1]);
    int x=0,y=0;
    pair <int, int> res={-1,-1};
    for (int i=0;i<N;i++){
        while (x<ve.size()&&ve[x].first<l[i]){
            update(ve[x].second,-1);
            x++;
        }
        while (y<ve.size()&&ve[y].first<=i){
            update(ve[y].second,1);
            y++;
        }
        res=max(res,{get(r[i])-get(i-1),-i});
    }
    return -res.second;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while (x<ve.size()&&ve[x].first<l[i]){
      |                ~^~~~~~~~~~
tournament.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while (y<ve.size()&&ve[y].first<=i){
      |                ~^~~~~~~~~~

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