Submission #414901

#	Time	Username	Problem	Language	Result	Execution time	Memory
414901		cpp219	Jousting tournament (IOI12_tournament)	C++14	49 / 100	70 ms	4896 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){
        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;
    for (ll i = 0;i < n;i++){
        total += pre[i];
        if (total > mx){
            mx = total; chosen = i;
        }
    }
    return chosen;
}

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"
      | 
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:87:12: warning: 'chosen' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     return chosen;
      |            ^~~~~~

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