oj.uz

Submission #559816

# Submission time Handle Problem Language Result Execution time Memory
559816 2022-05-10T16:43:06 Z ngpin04 Jousting tournament (IOI12_tournament) C++14
0 / 100
 18 ms 1432 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;
    assert(n <= 10);
    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);
}

//#include "grader.cpp"

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 1432 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -