oj.uz

Submission #481835

# Submission time Handle Problem Language Result Execution time Memory
481835 2021-10-22T03:02:52 Z Haruto810198 Jousting tournament (IOI12_tournament) C++17
100 / 100
 83 ms 15956 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define lsb(x) ((x)&(-(x)))

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 100010;

int BIT[MAX];
int n;

pii seg[MAX];
int seg_r[MAX];
vi edge[MAX];

int Max[MAX][20];

void modify(int pos, int val){
    while(pos <= n){
        BIT[pos] += val;
        pos += lsb(pos);
    }
}

int Find(int val){ // find smallest x s.t. pref[x] >= val
    int pos = 0;
    int sum = 0;
    for(int j = 19; j >= 0; j--){
        if(pos + (1<<j) <= n and sum + BIT[pos + (1<<j)] < val){
            sum += BIT[pos + (1<<j)];
            pos += (1<<j);
        }
    }
    return pos + 1;
}

int query_max(int ql, int qr){
    if(ql > qr) return -1;
    int rk = __lg(qr - ql + 1);
    return max(Max[ql][rk], Max[qr - (1<<rk) + 1][rk]);
}

int GetBestPosition(int N, int C, int R, int *K, int *st, int *ed){

    n = N;

    // BIT
    FOR(i, 1, n, 1){
        modify(i, 1);
        seg_r[i] = i;
    }

    // s, e: 0 -> 1

    FOR(i, 0, C-1, 1){
        st[i]++, ed[i]++;
        seg[i].F = Find(st[i]) - 1; // 1 -> 0
        seg[i].S = seg_r[ Find(ed[i]) ] - 1;

        seg_r[ Find(st[i]) ] = seg_r[ Find(ed[i]) ];
        FOR(j, 1, ed[i] - st[i], 1){
            modify(Find(st[i] + 1), -1);
        }
    }

    //cerr<<"segments : "<<endl;
    FOR(i, 0, C-1, 1){
        //cerr<<seg[i].F<<" "<<seg[i].S<<endl;
    }

    // sparse table
    FOR(i, 0, n-2, 1){
        Max[i][0] = K[i];
    }

    FOR(j, 1, 19, 1){
        FOR(i, 0, n-2, 1){
            if(i + (1<<(j-1)) <= n-2) Max[i][j] = max(Max[i][j-1], Max[i + (1<<(j-1))][j-1]);
            else Max[i][j] = Max[i][j-1];
        }
    }

    // win condition
    vector<pii> ev; // pos, val
    FOR(i, 0, C-1, 1){
        // win[l, r]: R at[l, r] and R > arr[l] ... arr[r - 1]
        if(R > query_max(seg[i].F, seg[i].S - 1)){
            ev.eb(seg[i].F, 1);
            ev.eb(seg[i].S + 1, -1);
            //cerr<<"win "<<seg[i].F<<" "<<seg[i].S<<endl;
        }
    }

    sort(ev.begin(), ev.end());

    int res_max = 0, res_id = 0, cur = 0;
    for(pii i : ev){
        cur += i.S;
        if(cur > res_max){
            res_max = cur;
            res_id = i.F;
        }
        //cerr<<i.F<<" "<<i.S<<endl;
    }

    return res_id;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 5 ms 3276 KB Output is correct
3 Correct 2 ms 3052 KB Output is correct
4 Correct 4 ms 3276 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 4 ms 3276 KB Output is correct
7 Correct 5 ms 3276 KB Output is correct
8 Correct 5 ms 3288 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Correct 4 ms 3276 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8292 KB Output is correct
2 Correct 78 ms 15332 KB Output is correct
3 Correct 36 ms 12524 KB Output is correct
4 Correct 83 ms 15956 KB Output is correct
5 Correct 79 ms 15464 KB Output is correct
6 Correct 71 ms 14964 KB Output is correct
7 Correct 81 ms 15920 KB Output is correct
8 Correct 76 ms 15936 KB Output is correct
9 Correct 35 ms 12100 KB Output is correct
10 Correct 33 ms 12260 KB Output is correct