Submission #559818

#	Time	Username	Problem	Language	Result	Execution time	Memory
559818		ngpin04	Jousting tournament (IOI12_tournament)	C++14	100 / 100	111 ms	8788 KiB

tournament

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int cnt[N];
int dp[N];
int mx[N];
int n;

void update(int pos, int val) {
    pos++;
    for (; pos <= n; pos += pos & -pos) 
        cnt[pos] += val;
}

int getval(int k) {
    int cur = 0;
    int num = 0;
    for (int i = 20; i >= 0; i--) if (cur + (1 << i) <= n) {
        if (num + cnt[cur + (1 << i)] <= k) {
            cur += (1 << i);
            num += cnt[cur];
        }
    }
    return cur;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    set <pair <int, int>> seg;
    for (int i = 0; i < n; i++) {
        seg.insert(mp(i, i));
        update(i, 1);
    }

    for (int i = 0; i < C; i++) {
        int l = S[i];
        int r = E[i];
        l = getval(l);
        r = getval(r + 1) - 1;
        while (true) {
            auto it = seg.lower_bound(mp(l, l));
            if (it == seg.end() || it->fi > r)
                break;
            maxi(mx[l], mx[it->fi]);
            if (it->se < r)
                maxi(mx[l], K[it->se]);
            seg.erase(it);
            update(it->fi, -1);
        }

        // cerr << "max(" << l << ", " << r - 1 << ") = " << mx[l] << "\n";
        seg.insert(mp(l, r));
        if (mx[l] < R) 
            dp[l]++, dp[r + 1]--;
        update(l, 1);
    }

    for (int i = 1; i < n; i++)
        dp[i] += dp[i - 1];

    return max_element(dp, dp + n) - dp;
}

//#include "grader.cpp"

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