oj.uz

Submission #559818

# Submission time Handle Problem Language Result Execution time Memory
559818 2022-05-10T16:55:14 Z ngpin04 Jousting tournament (IOI12_tournament) C++14
100 / 100
 111 ms 8788 KB 
#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.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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 304 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 1 ms 340 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 6 ms 712 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 6 ms 648 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3704 KB Output is correct
2 Correct 93 ms 8748 KB Output is correct
3 Correct 44 ms 6840 KB Output is correct
4 Correct 89 ms 8704 KB Output is correct
5 Correct 82 ms 8388 KB Output is correct
6 Correct 111 ms 8312 KB Output is correct
7 Correct 86 ms 8788 KB Output is correct
8 Correct 86 ms 8672 KB Output is correct
9 Correct 45 ms 6684 KB Output is correct
10 Correct 50 ms 7120 KB Output is correct