Submission #1197666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197666		Hamed_Ghaffari	Jousting tournament (IOI12_tournament)	C++20	100 / 100	72 ms	8776 KiB

tournament

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e5+5, inf = 1e9;

int n;

namespace seg1 {
    int seg[MXN<<2];
    bool lz[MXN<<2];
    void build(int l=0, int r=n, int id=1) {
        seg[id] = r-l;
        lz[id] = 0;
        if(r-l == 1) return;
        build(l, mid, lc);
        build(mid, r, rc);
    }
    inline void apply(int id) {
        seg[id] = 0;
        lz[id] = 1;
    }
    inline void push(int l, int r, int id) {
        if(r-l>1 && lz[id]) {
            apply(lc);
            apply(rc);
        }
        lz[id] = 0;
    }
    void upd(int s, int e, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e) return;
        if(s<=l && r<=e) return apply(id);
        push(l, r, id);
        upd(s, e, l, mid, lc);
        upd(s, e, mid, r, rc);
        seg[id] = seg[lc] + seg[rc];
    }
    int find(int x, int l=0, int r=n, int id=1) {
        if(seg[id]<x) return -1;
        if(r-l == 1) return l;
        push(l, r, id);
        int res = find(x, l, mid, lc);
        return res==-1 ? find(x-seg[lc], mid, r, rc) : res;
    }
}

namespace seg2 {
    pll seg[MXN<<2];
    ll lz[MXN<<2];
    void build(int l=0, int r=n, int id=1) {
        seg[id] = pll(0, -l);
        if(r-l == 1) return;
        build(l, mid, lc);
        build(mid, r, rc);
    }
    void upd(int s, int e, int x, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e) return;
        if(s<=l && r<=e) {
            seg[id].first += x;
            lz[id] += x;
            return;
        }
        upd(s, e, x, l, mid, lc);
        upd(s, e, x, mid, r, rc);
        seg[id] = max(seg[lc], seg[rc]);
        seg[id].first += lz[id];
    }
}

int GetBestPosition(int n, int C, int R, int *a, int *s, int *e) {
    ::n = n;
    seg1::build();
    for(int i=0; i<C; i++) {
        s[i] = seg1::find(s[i]+1);
        e[i] = seg1::find(e[i]+2);
        if(e[i]==-1) e[i] = n;
        e[i]--;
        seg1::upd(s[i]+1, e[i]+1);
    }
    vector<pii> segs;
    int lst=-1;
    for(int i=0; i<n-1; i++)
        if(a[i]>R) {
            if(i-lst>1)
                segs.push_back({lst+1, i});
            lst = i;
        }
    if(n-1-lst>1)
        segs.push_back({lst+1, n-1});
    pll ans = {-1, -1};
    seg2::build();
    for(int i=0; i<C; i++) {
        int pos = lower_bound(segs.begin(), segs.end(), pii(s[i]+1, 0))-segs.begin()-1;
        if(pos>=0 && segs[pos].second>=e[i])
            seg2::upd(s[i], e[i]+1, 1);
        else
            seg2::upd(s[i], e[i], -inf);
        ans = max(ans, seg2::seg[1]);
    }
    return -ans.second;
}

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