Submission #310521

#	Time	Username	Problem	Language	Result	Execution time	Memory
310521		lohacho	Jousting tournament (IOI12_tournament)	C++14	100 / 100	146 ms	12020 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1e5 + 4;
struct fenwick{
    vector < int > fenw;
    int N;
    fenwick(){}
    fenwick(int n):N(n){
        fenw.resize(N);
    }
    void push(int x, int val){
        for(int i = x; i < N; i += (i & -i)){
            fenw[i] += val;
        }
    }
    int get(int x){
        int rv = 0;
        for(int i = x; i; i -= (i & -i)){
            rv += fenw[i];
        }
        return rv;
    }
}lcnt(NS), cnt(NS);
vector<int> ls[NS], rs[NS];
vector<int> big;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for(int i = 0; i < N; ++i){
        lcnt.push(i + 1, 1);
    }
    big.push_back(-1);
    for(int i = 0; i < N; ++i){
        if(K[i] > R){
            big.push_back(i);
        }
    }
    function<int(int)> getpos = [&](int val){
        int low = 0, high = N, mid;
        while(low < high){
            mid = (low + high) >> 1;
            if(lcnt.get(mid) >= val){
                high = mid;
            }
            else{
                low = mid + 1;
            }
        }
        return low;
    };
    for(int i = 0; i < C; ++i){
        int l = getpos(S[i]), r = getpos(E[i] + 1) - 1;
        ls[l].push_back(r), rs[r].push_back(l);
        for(int val = S[i] + 1; val <= E[i]; ++val){
            int pos = getpos(S[i] + 1);
            lcnt.push(pos, -1);
        }
    }
    for(int i = 0; i < N; ++i){
        sort(ls[i].begin(), ls[i].end());
        sort(rs[i].begin(), rs[i].end());
        reverse(rs[i].begin(), rs[i].end());
        int r = lower_bound(big.begin(), big.end(), i) - big.begin();
        for(auto&lsr:ls[i]){
            if(lsr >= big[r]){
                break;
            }
            cnt.push(i + 1, 1), cnt.push(lsr + 2, -1);
        }
    }
    int j = (int)big.size() - 1, ans, mx = -1;
    for(int i = N - 1; i >= 0; --i){
        if(j >= 0 && big[j] == i){
            int lpos = lower_bound(big.begin(), big.end(), i) - big.begin() - 1;
            for(auto&l:rs[i]){
                if(l <= big[lpos]){
                    break;
                }
                cnt.push(l + 1, 1), cnt.push(i + 2, -1);
            }
            int rpos = lower_bound(big.begin(), big.end(), i + 1) - big.begin();
            for(auto&r:ls[i + 1]){
                if(r >= big[rpos]){
                    break;
                }
                cnt.push(i + 2, -1), cnt.push(r + 2, 1);
            }
            --j;
        }
        if(cnt.get(i + 1) >= mx){
            mx = cnt.get(i + 1);
            ans = i;
        }
    }
    return ans;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:98:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     return ans;
      |            ^~~

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