Submission #429807

#	Time	Username	Problem	Language	Result	Execution time	Memory
429807		someone	Jousting tournament (IOI12_tournament)	C++14	100 / 100	397 ms	19756 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51