Submission #414908

#	Time	Username	Problem	Language	Result	Execution time	Memory
414908		cpp219	Jousting tournament (IOI12_tournament)	C++14	100 / 100	76 ms	3276 KiB

tournament

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 9;
const ll sz = (1 << 17);
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;

ll st[2*sz + 9],st2[2*sz + 9];

void Add(ll a,ll b){
    a += sz; st[a] = b;
    while(a != 1){
        a >>= 1;
        st[a] = max(st[a*2],st[a*2 + 1]);
    }
}

void Add2(ll a,ll b){
    a += sz;
    while(a){
        st2[a] += b; a >>= 1;
    }
}

ll GetMax(ll b,ll e){
    b += sz; e += sz;
    ll kq = 0;
    while(b <= e){
        kq = max(kq,st[b]); kq = max(kq,st[e]);
        b = (b + 1) >> 1; e = (e - 1) >> 1;
    }
    return kq;
}

ll Find(ll a){
    ll root = 1;
    while(root < sz){
        root *= 2;
        if (st2[root] < a){
            a -= st2[root]; root++;
        }
    }
    return root - sz;
}

ll nxt(ll a){
    a += sz;
    while(!st2[a]) a = (a + 1) >> 1;
    while(a < sz){
        a <<= 1;
        if (!st2[a]) a++;
    }
    return a - sz;
}

ll pre[N];

ll GetBestPosition(ll n,ll C,ll R,ll *K,ll *S,ll *E){
    for (ll i = 0;i < n - 1;i++) Add(i,K[i]);
    for (ll i = 0;i <= n;i++) Add2(i,1);
    for (ll i = 0;i < C;i++){
        ll b = Find(S[i] + 1),e = Find(E[i] + 2) - 1;
        if (GetMax(b,e - 1) < R) pre[b]++,pre[e + 1]--;
        while(1){
            //cout<<b<<" ";
            b = nxt(b + 1); //cout<<"?";
            if (b > e) break;
            Add2(b,-1);
        }
    }
    //exit(0);
    ll total = 0,mx = 0,chosen = 0;
    for (ll i = 0;i < n;i++){
        total += pre[i];
        if (total > mx){
            mx = total; chosen = i;
        }
    }
    return chosen;
}
/*
ll n,C,R,k[N],s[N],e[N];


int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>C>>R;
    for (ll i = 0;i < n - 1;i++) cin>>k[i];
    for (ll i = 0;i < C;i++) cin>>s[i]>>e[i];
    cout<<GetBestPosition(n,C,R,k,s,e);
}
*/

Compilation message (stderr)

tournament.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
tournament.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |

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