Submission #1122470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122470		Sang	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1 ms	324 KiB

tournament

#include<bits/stdc++.h>
using namespace std;

#define _pbrngw_ Khánh Băng dthw nhất hệ mặt trời :>>
// #define int long long
#define ALL(a) (a).begin(), (a).end()
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, r, c, T[4*N][2], v[N], mx[N][20];
ii lazy[4*N], a[N];

void build(int id, int l, int r){
    if (l == r) {
        T[id][0] = T[id][1] = l;
        return;
    }
    int m = (l+r)/2;
    build(id*2, l, m);
    build(id*2+1, m+1, r);
    T[id][0] = max(T[id*2][0], T[id*2+1][0]);
    T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}

void down(int id){
    int val1 = lazy[id].fi, val2 = lazy[id].se;
    if (val2){
        T[id*2][0] = T[id*2+1][0] = val2;
        T[id*2][1] = T[id*2+1][1] = val2;
        lazy[id*2].se = lazy[id*2+1].se = val2;
        lazy[id*2].fi = lazy[id*2+1].fi = 0;
    }
    T[id*2][0] += val1;
    T[id*2+1][0] += val1;
    T[id*2][1] += val1;
    T[id*2+1][1] += val1;
    lazy[id*2].fi += val1;
    lazy[id*2+1].fi += val1;
    lazy[id] = {0, 0};
}

void update(int id, int l, int r, int u, int v, int val){
    if (l > v || r < u) return;
    if (u <= l && r <= v){
        T[id][0] += val;
        T[id][1] += val;
        lazy[id].fi += val;
        return;
    }
    int m = (l+r)/2;
    down(id);
    update(id*2, l, m, u, v, val);
    update(id*2+1, m+1, r, u, v, val);
    T[id][0] = max(T[id*2][0], T[id*2+1][0]);
    T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}

void update2(int id, int l, int r, int u, int v, int val){
    if (l > v || r < u) return;
    if (u <= l && r <= v){
        T[id][0] = T[id][1] = val;
        lazy[id] = {0, val};
        return;
    }
    int m = (l+r)/2;
    down(id);
    update2(id*2, l, m, u, v, val);
    update2(id*2+1, m+1, r, u, v, val);
    T[id][0] = max(T[id*2][0], T[id*2+1][0]);
    T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}

int get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return T[id][0];
    down(id);
    int m = (l+r)/2;
    return max(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
}

int getL(int id, int l, int r, int k){
    if (T[id][0] < k) return -1;
    if (l == r) return l;
    int m = (l+r)/2;
    down(id);
    int ans = getL(id*2, l, m, k);
    if (ans == -1) return getL(id*2+1, m+1, r, k);
    return ans;
}

int getR(int id, int l, int r, int k){
    if (T[id][1] > k) return -1;
    if (l == r) return l;
    int m = (l+r)/2;
    down(id);
    int ans = getR(id*2+1, m+1, r, k);
    if (ans == -1) return getR(id*2, l, m, k);
    return ans;
}

int getMax(int l, int r){
    int k = log2(r-l+1);
    return max(mx[l][k], mx[r-(1<<k)+1][k]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    n = N; c = C; r = R;
    ++r;
    FOR (i, 1, n-1) mx[i][0] = ++K[i - 1];
    build(1, 1, n);
    FOR (i, 1, c){
        int s, e; s = S[i-1] + 1; e = E[i-1] + 1;
        int L = getL(1, 1, n, s), R = getR(1, 1, n, e) ;
        a[i] = {L, R};
        // cout << L << ' ' << R << "\n";
        update2(1, 1, n, L, R, get(1, 1, n, 1, L-1)+1);
        update(1, 1, n, R+1, n,  - (e - s));
        // cout << get(1, 1, n, 5, 5) << "\n";
    }
    for (int j = 1; (1<<j) < n; j++){
        for (int i = 1; i + (1<<j) - 1 < n; i++){
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
        }
    }
    int ans = 0, pos = 1;
    FOR (i, 1, 4*n + 2) lazy[i] = {0, 0}, T[i][0] = T[i][1] = 0; 
    FOR (i, 1, c){
        if (getMax(a[i].fi, a[i].se - 1) < r){
            update(1, 1, n, a[i].fi, a[i].se, 1);
        } else update(1, 1, n, a[i].fi, a[i].se, -1e9);
        if (ans < T[1][0]){
            pos = getL(1, 1, n, T[1][0]);
            ans = T[1][0];
        } else if (ans == T[1][0]) pos = min(pos, getL(1, 1, n, ans));
    }
    return pos - 1;

}

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