oj.uz

Submission #64651

# Submission time Handle Problem Language Result Execution time Memory
64651 2018-08-05T09:50:16 Z someone_aa Jousting tournament (IOI12_tournament) C++17
100 / 100
 143 ms 16348 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
pair<int,int> intervals[maxn];
int lc[maxn], rc[maxn], n, r, q;
int bit[maxn], curr_intv[maxn], parent[maxn];
int pref[maxn], answ[maxn];

void update(int index, int val) {
    for(int i=index;i<=n;i+=i&(-i)) {
        bit[i] += val;
    }
}

int query(int x) {
    int sum = 0;
    for(int i=x;i>0;i-=i&(-i)) {
        sum += bit[i];
    }
    return sum;
}

void preprocess() {
    for(int i=0;i<=n;i++) {
        lc[i] = i - 1;
        rc[i] = i + 1;
    }
    rc[n] = -1;
}

int bin_search(int val) {
    int index = n;
    if(query(index) < val) return n+1;
    for(int cekor = n; cekor > 0; cekor/=2) {
        while(index - cekor >= 0 && query(index-cekor)>=val) index-=cekor;
    }
    return index;
}

int recursion(int i) {
    if(answ[i] != -1) return answ[i];

    int l = intervals[i].first;
    int r = intervals[i].second;
    int after = r - 1;
    int before = l - 1;
    int cnt = pref[after] - pref[before];

    if(cnt == 0) {
        answ[i] = 1;
        if(parent[i] != -1) answ[i] += recursion(parent[i]);
    }
    else {
        answ[i] = 0;
    }
    return answ[i];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N; r = R; q = C;
    preprocess();
    for(int i=1;i<=n;i++) update(i, 1);

    memset(curr_intv, -1, sizeof(curr_intv));
    memset(parent, -1, sizeof(parent));
    memset(answ, -1, sizeof(answ));

    for(int i=0;i<q;i++) {
        int l = bin_search(S[i]+1);
        int r = bin_search(E[i]+2) - 1;

        intervals[i] = mp(l, r);

        if(curr_intv[l] != -1) {
            parent[curr_intv[l]] = i;
            curr_intv[l] = i;
        }
        else curr_intv[l] = i;

        //cout<<"Q:"<<i<<" -> "<<l<<" "<<r<<"\n";
        for(int j=rc[l];j<=r && j!=-1;j=rc[j]) {
            //cout<<"upd: "<<j<<"\n";
            // set this value to 0

            if(curr_intv[j] != -1) {
                parent[curr_intv[j]] = i;
                curr_intv[j] = i;
            }
            else curr_intv[j] = i;

            rc[lc[j]] = rc[j];
            lc[rc[j]] = lc[j];

            update(j, -1);
        }
    }


    for(int i=1;i<n;i++) {
        pref[i] = pref[i-1];
        if(K[i-1] > r) pref[i]++;
    }

    int maxm = 0, ind = 1;
    for(int i=0;i<q;i++) {
        int curr = recursion(i);
        if(curr > maxm) {
            maxm = curr;
            ind = intervals[i].first;
        }
        else if(curr == maxm) {
            ind = min(ind, intervals[i].first);
        }
    }
    return ind - 1;
}

/*int arr[maxn], s[maxn], e[maxn];
int main() {
    //ifstream fin("input.txt");

    int n, c, r;
    cin>>n>>c>>r;

    for(int i=0;i<n-1;i++) cin>>arr[i];
    for(int i=0;i<c;i++) cin>>s[i]>>e[i];

    cout<<GetBestPosition(n, c, r, arr, s, e);

    return 0;
}*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 3 ms 1636 KB Output is correct
4 Correct 4 ms 1760 KB Output is correct
5 Correct 4 ms 1760 KB Output is correct
6 Correct 4 ms 1768 KB Output is correct
7 Correct 4 ms 1840 KB Output is correct
8 Correct 5 ms 1896 KB Output is correct
9 Correct 3 ms 1908 KB Output is correct
10 Correct 3 ms 1980 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1980 KB Output is correct
2 Correct 9 ms 2172 KB Output is correct
3 Correct 5 ms 2172 KB Output is correct
4 Correct 9 ms 2264 KB Output is correct
5 Correct 11 ms 2328 KB Output is correct
6 Correct 7 ms 2328 KB Output is correct
7 Correct 10 ms 2444 KB Output is correct
8 Correct 9 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 10 ms 2684 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3916 KB Output is correct
2 Correct 121 ms 8060 KB Output is correct
3 Correct 36 ms 8060 KB Output is correct
4 Correct 115 ms 10016 KB Output is correct
5 Correct 111 ms 11664 KB Output is correct
6 Correct 114 ms 12088 KB Output is correct
7 Correct 143 ms 14760 KB Output is correct
8 Correct 127 ms 16348 KB Output is correct
9 Correct 26 ms 16348 KB Output is correct
10 Correct 31 ms 16348 KB Output is correct