Submission #707860

#	Time	Username	Problem	Language	Result	Execution time	Memory
707860		Nhoksocqt1	Jousting tournament (IOI12_tournament)	C++17	100 / 100	107 ms	15748 KiB

tournament

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
#define round asirhq9rthqurtwhqw
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

struct Round {
    int s, e;
} round[MAXN], tmpr[MAXN];

struct Node {
    int sz, lastr;
} seg[4 * MAXN];

ii fen[MAXN];
int val[MAXN], tmp[MAXN], P[MAXN][18], posInTree[MAXN], nArr, numRound, R;

void build(int id, int l, int r) {
    if(l == r) {
        seg[id] = {1, l};
        posInTree[l] = id;
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    seg[id] = {seg[id << 1].sz + seg[id << 1 | 1].sz, seg[id << 1 | 1].lastr};
}

void update(int pos) {
    int id(posInTree[pos]);

    seg[id] = {0, 0};
    while(id > 1) {
        id >>= 1;
        seg[id].sz = seg[id << 1].sz + seg[id << 1 | 1].sz;
        seg[id].lastr = max(seg[id << 1].lastr, seg[id << 1 | 1].lastr);
    }
}

Node query(int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return {0, 0};

    if(u <= l && r <= v)
        return seg[id];

    int mid = (l + r) >> 1;
    Node ql = query(id << 1, l, mid, u, v), qr = query(id << 1 | 1, mid + 1, r, u, v);
    return {ql.sz + qr.sz, max(ql.lastr, qr.lastr)};
}

int query(int id, int l, int r, int &sz) {
    if(!sz)
        return 0;

    if(seg[id].sz <= sz) {
        sz -= seg[id].sz;
        return (sz == 0) ? seg[id].lastr : 0;
    }

    int mid = (l + r) >> 1;
    int ql = query(id << 1, l, mid, sz), qr = query(id << 1 | 1, mid + 1, r, sz);
    return max(ql, qr);
}

int findFirst(int x) {
    int l(1), r(x - 1), answer(x);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(query(1, 1, nArr, mid, x - 1).sz == 0) {
            answer = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return answer;
}

int findLast(int x) {
    int l(x + 1), r(nArr), answer(x);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(query(1, 1, nArr, x + 1, mid).sz == 0) {
            answer = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return answer;
}

inline int getMax(int l, int r) {
    int log = 31 - __builtin_clz(r - l + 1);
    return max(P[l][log], P[r - (1 << log) + 1][log]);
}

int brute(void) {
    int maxWin(0), pos(1);
    for (int i = 1; i <= nArr; ++i) {
        for (int j = 1; j < i; ++j)
            tmp[j] = val[j];

        tmp[i] = R;
        for (int j = i; j < nArr; ++j)
            tmp[j + 1] = val[j];

        int numWin(0), szNow(nArr);
        for (int i = 1; i <= numRound; ++i) {
            int s(tmpr[i].s), e(tmpr[i].e), maxp(0);
            for (int j = s; j <= e; ++j)
                maxp = max(maxp, tmp[j]);

            numWin += (maxp == R);
            for (int j = e + 1; j <= szNow; ++j)
                tmp[s + j - e] = tmp[j];

            tmp[s] = maxp;
            szNow -= e - s;
        }

        if(numWin > maxWin) {
            maxWin = numWin;
            pos = i;
        }
    }

    cout << maxWin << ' ' << pos << '\n';
    return pos - 1;
}

void modify(int i, ii v) {
    for (; i > 0; i -= i & -i) {
        if(fen[i].fi < v.fi || fen[i].fi == v.fi && fen[i].se > v.se)
            fen[i] = v;
    }
}

ii get(int i) {
    ii res = {0, i};
    for (; i <= nArr; i += i & -i) {
        if(res.fi < fen[i].fi || res.fi == fen[i].fi && res.se > fen[i].se)
            res = fen[i];
    }

    return res;
}

int leftPos[MAXN];

int GetBestPosition(int _N, int _C, int _R, int _K[], int _S[], int _E[]) {
    nArr = _N, numRound = _C, R = _R;
    for (int i = 1; i < nArr; ++i) {
        val[i] = _K[i - 1];
        P[i][0] = val[i];
    }

    for (int i = 1; i <= nArr; ++i)
        leftPos[i] = i;

    for (int j = 1; (1 << j) < nArr; ++j) {
        for (int i = 1; i + (1 << j) - 1 < nArr; ++i)
            P[i][j] = max(P[i][j - 1], P[i + (1 << (j - 1))][j - 1]);
    }

    build(1, 1, nArr);
    for (int i = 1; i <= numRound; ++i) {
        tmpr[i] = {_S[i - 1] + 1, _E[i - 1] + 1};

        int tmp;
        //cout << i << ' ' << _S[i - 1] + 1 << ' ' << _E[i - 1] + 1 << ": ";
        round[i].s = query(1, 1, nArr, (tmp = _S[i - 1] + 1));
        round[i].e = query(1, 1, nArr, (tmp = _E[i - 1] + 1));
        //cout << round[i].s << ' ' << round[i].e << '\n';

        leftPos[round[i].e] = leftPos[round[i].s];
        round[i] = {leftPos[round[i].s], round[i].e};
        tmp = _E[i - 1] - _S[i - 1];
        int lasty(round[i].e - 1);
        while(tmp--) {
            int pos = query(1, 1, nArr, round[i].s, lasty).lastr;
            update(pos);
        }
    }

    //cout << brute() << '\n';

    for (int i = 1; i <= nArr; ++i)
        fen[i] = {0, 1e9};

    sort(round + 1, round + numRound + 1, [](const Round &a, const Round &b) {
        return (a.e != b.e) ? a.e < b.e : a.s > b.s;
    });

    int maxWin(0), pos(1);
    for (int i = 1; i <= numRound; ++i) {
        ii res = get(round[i].s);
        ++res.fi;
        modify(round[i].s, res);

        //cout << i << ' ' << round[i].s << ' ' << round[i].e << ' ' << res.fi << ' ' << res.se << '\n';
        if(getMax(round[i].s, round[i].e - 1) < R) {
            if(maxWin < res.fi || maxWin == res.fi && pos > res.se) {
                maxWin = res.fi;
                pos = res.se;
            }
        }
    }

    //cout << maxWin << ' ' << pos << '\n';
    return pos - 1;
}

Compilation message (stderr)

tournament.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
tournament.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
tournament.cpp: In function 'void modify(int, ii)':
tournament.cpp:159:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  159 |         if(fen[i].fi < v.fi || fen[i].fi == v.fi && fen[i].se > v.se)
      |                                                  ^
tournament.cpp: In function 'ii get(int)':
tournament.cpp:167:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  167 |         if(res.fi < fen[i].fi || res.fi == fen[i].fi && res.se > fen[i].se)
      |                                                      ^
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:228:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  228 |             if(maxWin < res.fi || maxWin == res.fi && pos > res.se) {
      |                                                    ^

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