oj.uz

Submission #429807

# Submission time Handle Problem Language Result Execution time Memory
429807 2021-06-16T09:46:07 Z someone Jousting tournament (IOI12_tournament) C++14
100 / 100
 397 ms 19756 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll deb, fin, a, b, mini, maxi;
};

struct Tour {
    ll deb, fin;
};

const ll T = 17, M = 1 << T, N = 2*M, INF = 1e10;

Node node[N];
Tour tour[N];
ll n, nbR, rang[N], tabCumul[N];

void initLazy1() {
    for(ll i = M; i < N; i++) {
        node[i].deb = i - M;
        node[i].fin = i - M + 1;
    }
    for(ll i = M-1; i > 0; i--) {
        node[i].deb = node[i*2].deb;
        node[i].fin = node[i*2+1].fin;
    }
    for(ll i = 1; i < N; i++) {
        node[i].a = 1;
        node[i].b = 0;
        node[i].mini = node[i].deb;
        node[i].maxi = node[i].fin - 1;
    }
}

void initLazy2() {
    for(ll i = 1; i < N; i++) {
        node[i].a = 1;
        node[i].b = 0;
    }
    for(int i = M; i < N; i++)
        node[i].mini = node[i].maxi = rang[i - M];
    for(int i = M-1; i > 0; i--) {
        node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
        node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
    }
}

void applyOp(ll i, ll a, ll b) {
    node[i].a = node[i].a * a;
    node[i].b = node[i].b * a + b;
    node[i].mini = node[i].mini * a + b;
    node[i].maxi = node[i].maxi * a + b;
    if(node[i].mini > node[i].maxi)
        swap(node[i].mini, node[i].maxi);
}

ll update(ll i, ll deb, ll fin, ll a, ll b) {
    if(fin <= node[i].deb || node[i].fin <= deb)
        return -INF;
    if(deb <= node[i].deb && node[i].fin <= fin) {
        applyOp(i, a, b);
        return node[i].maxi;
    }
    ll l = i*2, r = l+1;
    applyOp(l, node[i].a, node[i].b);
    applyOp(r, node[i].a, node[i].b);

    node[i].a = 1;
    node[i].b = 0;

    int max1 = update(l, deb, fin, a, b),
        max2 = update(r, deb, fin, a, b);

    node[i].mini = min(node[l].mini, node[r].mini);
    node[i].maxi = max(node[l].maxi, node[r].maxi);

    return max(max1, max2);
}

ll search(ll i, ll val) {
    if(i >= M)
        return i - M;
    ll l = i*2, r = l+1;
    applyOp(l, node[i].a, node[i].b);
    applyOp(r, node[i].a, node[i].b);
    node[i].a = 1;
    node[i].b = 0;
    if(node[l].maxi >= val)
        return search(l, val);
    return search(r, val);
}

void initTour() {
    initLazy1();
    for(ll i = 0; i < nbR; i++) {
        ll deb = search(1, tour[i].deb),
            fin = search(1, tour[i].fin + 1);

        ll val = update(1, deb, deb + 1, 1, 0);
        update(1, deb, fin, 0, val);
        update(1, fin, M, 1, tour[i].deb - tour[i].fin);

        tour[i].deb = deb;
        tour[i].fin = fin;
    }
}

int GetBestPosition(int n1, int c1, int r1, int *K, int *S, int *E) {
    n = n1;
    nbR = c1;
    rang[0] = r1;

    for(ll i = 1; i < n; i++)
        rang[i] = K[i-1];
    for(ll i = 0; i < nbR; i++) {
        tour[i].deb = S[i];
        tour[i].fin = E[i];
    }

    initTour();
    initLazy2();

    for(int i = 0; i < nbR; i++) {
        int maxi = update(1, tour[i].deb + 1, tour[i].fin, 1, 0);
        //cout << tour[i].deb + 1 << ' ' << tour[i].fin << ' ' << maxi << '\n';
        if(maxi < rang[0]) {
            tabCumul[tour[i].deb]++;
            tabCumul[tour[i].fin]--;
        }
    }
    for(int i = 1; i < N; i++)
        tabCumul[i] += tabCumul[i-1];
    /*for(int i = 0; i < 5; i++)
        cout << tabCumul[i] << ' ';
    cout << '\n';*/
    int imax = 0;
    for(int i = 1; i < N; i++)
        if(tabCumul[i] > tabCumul[imax])
            imax = i;
    return imax;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14668 KB Output is correct
2 Correct 13 ms 14668 KB Output is correct
3 Correct 14 ms 14668 KB Output is correct
4 Correct 15 ms 14668 KB Output is correct
5 Correct 14 ms 14668 KB Output is correct
6 Correct 14 ms 14688 KB Output is correct
7 Correct 13 ms 14668 KB Output is correct
8 Correct 15 ms 14684 KB Output is correct
9 Correct 13 ms 14668 KB Output is correct
10 Correct 13 ms 14632 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14692 KB Output is correct
2 Correct 29 ms 14704 KB Output is correct
3 Correct 15 ms 14668 KB Output is correct
4 Correct 28 ms 14796 KB Output is correct
5 Correct 26 ms 14756 KB Output is correct
6 Correct 23 ms 14856 KB Output is correct
7 Correct 30 ms 14900 KB Output is correct
8 Correct 36 ms 14876 KB Output is correct
9 Correct 17 ms 14668 KB Output is correct
10 Correct 27 ms 14784 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15868 KB Output is correct
2 Correct 348 ms 19752 KB Output is correct
3 Correct 44 ms 16504 KB Output is correct
4 Correct 361 ms 19756 KB Output is correct
5 Correct 397 ms 19560 KB Output is correct
6 Correct 228 ms 18500 KB Output is correct
7 Correct 336 ms 19732 KB Output is correct
8 Correct 342 ms 19748 KB Output is correct
9 Correct 24 ms 16404 KB Output is correct
10 Correct 41 ms 16580 KB Output is correct