Submission #287923

#	Time	Username	Problem	Language	Result	Execution time	Memory
287923		ToMmyDong	Jousting tournament (IOI12_tournament)	C++11	49 / 100	958 ms	9204 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(i) i.begin(), i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& __printRng (ostream& os, IT bg, IT ed) {
    for (IT it=bg;it!=ed;it++) {
        if (it == bg) os << "{" << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T> &vec) {
    return __printRng(os, ALL(vec));
}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S> &pa) {
    return os << "{" << pa.X << "," << pa.Y << "}";
}
#else
#define debug(...)
#endif

typedef pair<int,int> pii;
const int MAXN = 100005;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rk;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> fid;

int L[MAXN], R[MAXN], n;
vector<int> in[MAXN], out[MAXN];

int seg[MAXN*2], sn;
void build () {
    for (int i=sn-1; i>0; i--) {
        seg[i] = max(seg[i<<1], seg[i<<1|1]);
    }
}

int qry (int l, int r) {
    int ret = 0;
    for (l+=sn, r+=sn; l<r; l>>=1, r>>=1) {
        if (l&1) ret = max(ret, seg[l++]);
        if (r&1) ret = max(ret, seg[--r]);
    }
    return ret;
}
int GetBestPosition(int N, int C, int Z, int *K, int *S, int *E) {
    int r, c;
    n = N;
    sn = n-1;
    c = C;
    r = Z;
    vector<pii> fg;

    for (int i=0; i<n; i++) {
        rk.insert(i);
        L[i] = R[i] = i;
    }
    for (int i=0; i<c; i++) {
        auto ptr = rk.find_by_order(S[i]);
        int len = E[i] - S[i] + 1;

        vector<int> rmv;
        int lid = *ptr;
        int cl = L[lid];
        int cr = R[lid];
        for (int j=0; j<len-1; j++) {
            ptr++;
            rmv.emplace_back(*ptr);
        }
        for (int v : rmv) {
            cl = min(cl, L[v]);
            cr = max(cr, R[v]);
            in[cl].emplace_back(i);
            out[cr].emplace_back(i);
            rk.erase(v);
        }
        L[lid] = cl;
        R[lid] = cr;

        fg.emplace_back(cl, cr);
    }

    debug(fg);
    assert(rk.size() == 1);
    for (int i=0; i<n-1; i++) {
        seg[i+sn] = K[i];
    }
    build();
    
    pii ans = {-1, 0};
    for (int i=0; i<n; i++) {
        for (int id : in[i]) fid.insert(id);

//        int sl = -1, sr = SZ(fid);
//        while (sl < sr - 1) {
//            int sm = (sl + sr) >> 1;
//            pii rng = fg[*fid.find_by_order(sm)];
//            if (rng.X == i) rng.X++;
//            rng.Y--;
//            if (qry(rng.X, rng.Y + 1) < r) {
//                sl = sm;
//            } else {
//                sr = sm;
//            }
//        }

        int sr = 0;
        for (int id : fid) {
            pii rng = fg[id];
            rng.Y--;
            if (qry(rng.X, rng.Y + 1) < r) sr++;
        }
        ans = max(ans, {sr, -i});

        for (int id : out[i]) fid.erase(id);
    }
    debug(ans);
    return -ans.Y;

}

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