Submission #977429

#	Time	Username	Problem	Language	Result	Execution time	Memory
977429		fzyzzz_z	Jousting tournament (IOI12_tournament)	C++17	0 / 100	28 ms	4948 KiB

tournament

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

using ll = long long; 

const int N = 100000;

int t[2 * N]; 

int sum(int x, int y) { return x + y; }
int mv(int x, int y) { return min(x, y); }

void upd(int l, int r, int v, int (*f)(int, int)) {
    l += N; 
    r += N + 1; 
    for (; l < r; l /= 2, r /= 2) {
        if (l & 1) {
            t[l] = f(t[l], v);
            l++; 
        } if (r & 1) {
            r--; 
            t[r] = f(t[r], v);
        }
    }
}
int get(int x, int s, int (*f)(int, int)) { 
    for (x += N; x > 0; x /= 2) s = f(s, t[x]); 
    return s; 
}

int bt[2 * 131072], lt[2 * 131072]; 
void push(int ind, int L, int R) {
    if (!lt[ind]) return; 
    bt[ind] = 0; 
    if (L != R) {
        lt[2 * ind] += lt[ind]; 
        lt[2 * ind + 1] += lt[ind]; 
    }
    lt[ind] = 0; 
}
void upd2(int l, int r, int L = 0, int R = 131072 - 1, int ind = 1) {
    push(ind, L, R); 
    if (l <= L && R <= r) {
        lt[ind] = 1; 
        push(ind, L, R); 
        return; 
    }
    if (l > R || L > r) return; 
    int M = (L + R) / 2; 
    upd2(l, r, L, M, 2 * ind); 
    upd2(l, r, M + 1, R, 2 * ind + 1); 
    bt[ind] = bt[2 * ind] + bt[2 * ind + 1]; 
}
int ff(int v, int L = 0, int R = 131072 - 1, int ind = 1) {
    // if (L == R) cout << "ans  " << L << '\n';
    if (L == R) return L; 

    // cout << "! " << L << ' ' << R << ' ' << v << '\n';

    int M = (L + R) / 2; 
    push(2 * ind, L, M); 
    push(2 * ind + 1, M + 1, R); 
    int res; 
    if (bt[2 * ind] >= v) {
        res = ff(v, L, M, 2 * ind); 
    } else {
        res = ff(v - bt[2 * ind], M + 1, R, 2 * ind + 1); 
    }
    bt[ind] = bt[2 * ind] + bt[2 * ind + 1]; 
    return res; 
}

int brute(int n, int m, int k, int a[], int sl[], int sr[]) {
    int res = 0, mx = 0; 
    for (int p = 0; p <= n; ++p) {
        vector<int> v; 
        int cs = 0; 
        for (int i = 0; i < n - 1; ++i) v.push_back(a[i]); 
        if (p == n) v.push_back(k); 
        else v.insert(v.begin() + p, k); 
        for (int t = 0; t < m; ++t) {
            int w = *max_element(v.begin() + sl[t], v.begin() + sr[t] + 1); 
            if (w == k) cs++; 
            v.erase(v.begin() + sl[t], v.begin() + sr[t] + 1); 
            if (sl[t] != (int)v.size()) v.insert(v.begin() + sl[t], w); 
            else v.push_back(w); 
        }
        if ((cs > mx)) {
            mx = cs; 
            res = p; 
        }
    }
    return res; 
}

int GetBestPosition(int n, int m, int k, int *a, int *sl, int *sr) {
    for (int i = 0; i < 131072; ++i) {
        bt[i + N] = 1; 
        lt[i] = lt[i + N] = 0; 
    }
    for (int i = 131071; i > 0; --i) {
        bt[i] = bt[2 * i] + bt[2 * i + 1]; 
    }
    

    for (int i = 0; i < m; ++i) {
        int l = sl[i], r = sr[i];
        sl[i] = ff(l + 1); 
        sr[i] = ff(r + 1); 

        // cout << l << ' ' << r << '\n';
        // cout << sl[i] << ' ' << sr[i] << "\n\n";

        upd2(sl[i] + 1, sr[i]); 
    }

    vector<int> p(n + 1, 0); 
    for (int i = 0; i < n - 1; ++i) {
        p[i + 1] = p[i] + (k < a[i]); 
    }
    p[n] = p[n - 1]; 

    // time of earliest bad segment
    for (int i = 0; i < 2 * N; ++i) {
        t[i] = m; 
    }
    // return 0; 
    for (int i = m - 1; i >= 0; --i) {
        assert(sl[i] <= sr[i] && sr[i] <= n - 1); 
        if (p[sr[i]] - p[sl[i]] != 0) {
            upd(sl[i], sr[i], i, mv); 
            // cout << "! " << sl[i] << ' ' << sr[i] << '\n';
        }
    } 

    vector<vector<int>> f(m); 
    int ans = 0, mx = 0; 
    for (int i = 0; i < n; ++i) {
        int v = get(i, m, mv); 
        if (v > 0) f[v - 1].push_back(i); 
    }

    // for each f[i] cnt # of segs that contain i 
    for (int i = 0; i < 2 * N; ++i) {
        t[i] = 0; 
    }
    for (int i = 0; i < m; ++i) {
        upd(sl[i], sr[i], 1, sum); 
        for (auto x: f[i]) {
            int v = get(x, 0, sum); 
            // cout << x << ' ' << v << '\n';
            if ((v > mx) || (v == mx && x < ans)) {
                ans = x; 
                mx = v; 
            }
        }
    }

    return ans; 
}

// int32_t main() {
//     ios_base::sync_with_stdio(false); 
//     cin.tie(0); 

//     int n, m, k; 
//     cin >> n >> m >> k; 
//     int a[n - 1]; 
//     for (int i = 0; i < n - 1; ++i) cin >> a[i]; 
//     int l[m], r[m];
//     for (int i = 0; i < m; ++i) {
//         cin >> l[i] >> r[i]; 
//     }

//     cout << brute(n, m, k, a, l, r)  << '\n';
//     cout << GetBestPosition(n, m, k, a, l, r); 
//     return 0; 
// }

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