oj.uz

Submission #711763

# Submission time Handle Problem Language Result Execution time Memory
711763 2023-03-17T12:40:19 Z lukameladze Jousting tournament (IOI12_tournament) C++14
100 / 100
 104 ms 5324 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int MX = 3e5 + 5;
int n, tree[4 * MX], a[MX],tree_f[MX];
void build(int node, int le, int ri) {
    if (le == ri) {
        tree[node] = a[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2 * node, le,mid);
    build(2 * node + 1, mid + 1, ri);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
int getmax(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return max(getmax(2 * node, le, mid, start, end), getmax(2 * node + 1, mid + 1, ri, start,end));
}
void update(int idx, int val) {
    for (int i = idx; i < MX; i+=i&(-i)) {
        tree_f[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree_f[i];
    }
    return pas;
}
int get(int idx) {
    int le = 1, ri = n, ans = n + 1;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (getans(mid) >= idx) {
            ans = mid;
            ri = mid - 1;
        } else le = mid + 1;
    }
    return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    for(int i = 0; i < C; i++) {
        S[i]++; E[i]++;
    }
    for (int i = 1; i <= n - 1; i++) {
        a[i] = K[i - 1];
    }
    build(1,1,n - 1);
    for (int i = 1; i <= n; i++) {
        update(i, 1);
    }
    vector <int> pr; 
    pr = vector <int> (n + 5, 0);
    for (int i = 0; i < C; i++) {
        int st = get(S[i]);
        int nd = get(E[i] + 1) - 1;
        vector <int> v;
        for (int j = S[i] + 1; j <= E[i]; j++) {
            v.pb(get(j));
        }
        for (int x : v) update(x, -1);
        if (getmax(1,1,n - 1,st, nd - 1) < R) {
            pr[st]++; pr[nd]--;
        }
    }
    int res = -1, ret = 0;
    for (int i = 1; i <= n - 1; i++) {
        pr[i] += pr[i - 1];
        if (pr[i] > res) {
            res = pr[i];
            ret = i;
        }
    }
    return ret - 1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 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 340 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 5 ms 576 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 5 ms 568 KB Output is correct
5 Correct 4 ms 576 KB Output is correct
6 Correct 4 ms 444 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 6 ms 596 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2460 KB Output is correct
2 Correct 102 ms 5196 KB Output is correct
3 Correct 37 ms 4168 KB Output is correct
4 Correct 101 ms 5320 KB Output is correct
5 Correct 104 ms 5072 KB Output is correct
6 Correct 99 ms 4560 KB Output is correct
7 Correct 101 ms 5292 KB Output is correct
8 Correct 103 ms 5324 KB Output is correct
9 Correct 32 ms 4040 KB Output is correct
10 Correct 44 ms 3548 KB Output is correct