Submission #287954

#	Time	Username	Problem	Language	Result	Execution time	Memory
287954		ToMmyDong	Jousting tournament (IOI12_tournament)	C++11	100 / 100	448 ms	16364 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
#define eb emplace_back
#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]);
            rk.erase(v);
        }
        L[lid] = cl;
        R[lid] = cr;
        in[cl].emplace_back(i);
        out[cr].emplace_back(i);

        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);
        debug(in[i], out[i]);

        int sl = -1, sr = SZ(fid);
#ifdef tmd
            __printRng(cerr, ALL(fid));
#endif
        while (sl < sr - 1) {
            int sm = (sl + sr) >> 1;
            pii rng = fg[*fid.find_by_order(sm)];
            rng.Y--;

            int rn = qry(rng.X, rng.Y + 1);
            debug(i, rng, rn, sm);
            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++;
//        }
#ifdef tmd
        vector<int> cur;
        int val = 0;
        for (int j=0,ptr=0; j<n; j++) {
            if (j == i) cur.eb(r);
            else cur.eb(K[ptr++]);
        }
        for (int j=0; j<c; j++) {
            vector<int> nw;
            for (int k=0; k<S[j]; k++) {
                nw.eb(cur[k]);
            }
            int mx = 0;
            for (int k=S[j]; k<=E[j]; k++) {
                mx = max(mx, cur[k]);
            }
            nw.eb(mx);
            for (int k=E[j]+1;k<SZ(cur);k++) {
                nw.eb(cur[k]);
            }
            cur = nw;
            val += mx == r;
        }
        if (val != sr) {
            debug(i, val, sr);
            cout << "FATAL ERROR" << endl;
            debug(n, c, r);
            for (int j=0; j<n-1; j++) {
                cout << K[j] << " ";
            }
            cout << endl;
            for (int j=0; j<c; j++) cout << S[j] << " " << E[j] << endl;
            return -1;
        }
#endif
        ans = max(ans, {sr, -i});

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

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:116:17: warning: unused variable 'rn' [-Wunused-variable]
  116 |             int rn = qry(rng.X, rng.Y + 1);
      |                 ^~

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