oj.uz

Submission #756023

# Submission time Handle Problem Language Result Execution time Memory
756023 2023-06-10T21:58:43 Z Noble_Mushtak Jousting tournament (IOI12_tournament) C++14
100 / 100
 420 ms 34784 KB 
//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(num i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

#include <bits/extc++.h> /** keep-include */
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
//insert(k) inserts item k
//find_by_order(k) returns an iterator to the element which is bigger than k items
//order_of_key(k) returns number of items < k

vector<vi> treeJump(vi& P){
	int on = 1, d = 1;
	while(on < sz(P)) on *= 2, d++;
	vector<vi> jmp(d, P);
	rep(i,1,d) rep(j,0,sz(P))
		jmp[i][j] = jmp[i-1][jmp[i-1][j]];
	return jmp;
}

int jmp(vector<vi>& tbl, int nod, int steps){
	rep(i,0,sz(tbl))
		if(steps&(1<<i)) nod = tbl[i][nod];
	return nod;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    num treeSz = N+C;
    
    vector<num> initVals(N);
    initVals[C] = R;
    REPI(i, N-1) initVals[i+1] = K[i];

    vi par(treeSz);
    vector<vector<num>> children(treeSz);
    vector<pair<num,num>> intervals(treeSz);
    Tree<pair<num,num>> curOrder;
    REPI(i, N) {
        curOrder.insert({i, C+i});
        intervals[C+i] = {i,i};
    }
    REPI(i, C) {
        num newIdx = -1;
        num curV = C-i-1;
        num st = S[i];
        num nd = E[i];
        while (st <= nd) {
            auto it = curOrder.find_by_order(st);
            if (newIdx == -1) {
                newIdx = it->first;
                intervals[curV] = intervals[it->second];
            } else {
                intervals[curV].second = intervals[it->second].second;
            }
            children[curV].push_back(it->second);
            par[it->second] = curV;
            curOrder.erase(it);
            --nd;
        }
        assert(newIdx != -1);
        curOrder.insert({newIdx, curV});
    }
    auto tbl = treeJump(par);

    vector<num> segtree(2*N);
    REPI(i, N) segtree[N+i] = initVals[i];
    for (num i = N-1; i >= 1; --i) segtree[i] = max(segtree[2*i], segtree[2*i+1]);
    auto update = [&](num idx, num y) {
                      num curIdx = idx+N;
                      segtree[curIdx] = y;
                      while (curIdx > 1) {
                          curIdx >>= 1;
                          segtree[curIdx] = max(segtree[2*curIdx], segtree[2*curIdx+1]);
                      }
                  };
    auto query = [&](num idx1, num idx2) {
                     num leftIdx = idx1+N, rightIdx = idx2+N+1;
                     num ans = 0;
                     while (leftIdx < rightIdx) {
                         if (leftIdx & 1) ans = max(ans, segtree[leftIdx]), ++leftIdx;
                         if (rightIdx & 1) --rightIdx, ans = max(ans, segtree[rightIdx]);
                         leftIdx >>= 1, rightIdx >>= 1;
                     }
                     return ans;
                 };

    num roundsWon = 0, bestPos = 0;
    REPI(i, N) {
        if (i > 0) {
            update(i-1, K[i-1]);
            update(i, R);
        }
        num leftAns = 0, rightAns = C;
        while (leftAns < rightAns) {
            num mid = (leftAns+rightAns+1)/2;
            num curAns = jmp(tbl, C+i, mid);
            if (query(intervals[curAns].first, intervals[curAns].second) == R) leftAns = mid;
            else rightAns = mid-1;
        }
        if (leftAns > roundsWon) {
            roundsWon = leftAns;
            bestPos = i;
        }
        //cout << leftAns << " " << i << " | " << roundsWon << " " << bestPos << "\n";
    }
    return bestPos;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 15 ms 1668 KB Output is correct
3 Correct 7 ms 980 KB Output is correct
4 Correct 14 ms 1876 KB Output is correct
5 Correct 12 ms 1660 KB Output is correct
6 Correct 10 ms 1648 KB Output is correct
7 Correct 13 ms 1772 KB Output is correct
8 Correct 12 ms 1748 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 13 ms 1864 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 14948 KB Output is correct
2 Correct 408 ms 32444 KB Output is correct
3 Correct 218 ms 17948 KB Output is correct
4 Correct 420 ms 34784 KB Output is correct
5 Correct 380 ms 31384 KB Output is correct
6 Correct 327 ms 30008 KB Output is correct
7 Correct 400 ms 32472 KB Output is correct
8 Correct 397 ms 33136 KB Output is correct
9 Correct 138 ms 16844 KB Output is correct
10 Correct 206 ms 22004 KB Output is correct