oj.uz

Submission #310521

# Submission time Handle Problem Language Result Execution time Memory
310521 2020-10-07T08:43:49 Z lohacho Jousting tournament (IOI12_tournament) C++14
100 / 100
 146 ms 12020 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5760 KB Output is correct
2 Correct 4 ms 5760 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 5 ms 5888 KB Output is correct
5 Correct 4 ms 5760 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 5888 KB Output is correct
8 Correct 5 ms 5888 KB Output is correct
9 Correct 5 ms 5760 KB Output is correct
10 Correct 5 ms 5760 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5888 KB Output is correct
2 Correct 10 ms 6144 KB Output is correct
3 Correct 6 ms 5888 KB Output is correct
4 Correct 11 ms 6272 KB Output is correct
5 Correct 9 ms 6144 KB Output is correct
6 Correct 9 ms 6016 KB Output is correct
7 Correct 10 ms 6144 KB Output is correct
8 Correct 10 ms 6144 KB Output is correct
9 Correct 7 ms 5888 KB Output is correct
10 Correct 11 ms 6144 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8316 KB Output is correct
2 Correct 146 ms 12016 KB Output is correct
3 Correct 56 ms 7160 KB Output is correct
4 Correct 141 ms 11996 KB Output is correct
5 Correct 141 ms 11764 KB Output is correct
6 Correct 135 ms 10488 KB Output is correct
7 Correct 144 ms 12020 KB Output is correct
8 Correct 144 ms 12020 KB Output is correct
9 Correct 65 ms 7420 KB Output is correct
10 Correct 68 ms 7288 KB Output is correct