oj.uz

Submission #501296

# Submission time Handle Problem Language Result Execution time Memory
501296 2022-01-02T18:43:22 Z doowey Jousting tournament (IOI12_tournament) C++14
100 / 100
 235 ms 22312 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

vector<int> ord;

const int N = (int)2e5 + 10;

struct Node{
    int cnt;
    int lazy;
};

Node T[N * 4 + 512];
int id[N];

void build(int node, int cl, int cr){
    T[node].cnt = cr - cl + 1;
    if(cl == cr)
        return;
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
}

int n;

void push(int node, int cl, int cr){
    if(T[node].lazy){
        T[node].cnt=0;
        if(cl != cr){
            T[node * 2].lazy = 1;
            T[node * 2 + 1].lazy = 1;
        }
        T[node].lazy = 0;
    }
}

void reset(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = 1;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    reset(node * 2, cl, mid, tl, tr);
    reset(node * 2 + 1, mid + 1, cr, tl, tr);
    T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}


int get(int node, int cl, int cr, int p){
    if(cl == cr){
        return cl;
    }
    int mid = (cl + cr) / 2;
    push(node * 2, cl, mid);
    push(node * 2 + 1, mid + 1, cr);
    T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
    if(T[node * 2].cnt >= p)
        return get(node * 2, cl, mid, p);
    else
        return get(node * 2 + 1, mid + 1, cr, p - T[node * 2].cnt);
}

const int LOG = 18;
int par[LOG][N];
pii segm[N];

int high[N * 2];

void upd(int iq, int v){
    iq += n;
    high[iq] = v;
    iq /= 2;
    while(iq > 0){
        high[iq] = max(high[iq * 2], high[iq * 2 + 1]);
        iq /= 2;
    }
}

int get_high(int li, int ri){
    li += n;
    ri += n;
    int res = -1;
    while(li <= ri){
        if(li % 2 == 1) res = max(res, high[li ++ ]);
        if(ri % 2 == 0) res = max(res, high[ri -- ]);
        li /= 2;
        ri /= 2;
    }
    return res;
}

int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) {
    ord.push_back(R);
    n = _N;
    for(int i = 0 ; i < n - 1; i ++ ){
        ord.push_back(K[i]);
    }
    for(int i = 0 ; i < n; i ++ ){
        id[i] = i;
        segm[i] = mp(i, i);
    }
    build(1, 0, n - 1);
    int gl, gr;
    int m = n + C;
    int el, er;
    int tl, tr;
    int nid;
    for(int i = 0 ; i < LOG; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            par[i][j] = -1;
        }
    }
    for(int i = 0 ; i < C; i ++ ){
        el = S[i];
        er = E[i];
        el ++ ;
        er ++ ;
        tl=n;
        tr=0;
        for(int j = el; j <= er; j ++ ){
            nid = get(1, 0, n - 1, j);
            tl=min(tl,segm[id[nid]].fi);
            tr=max(tr,segm[id[nid]].se);
            par[0][id[nid]] = n + i;
        }
        reset(1, 0, n - 1, tl + 1, tr);
        segm[n + i] = mp(tl, tr);
        id[tl] = n + i;
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < m ; i ++ ){
            if(par[lg-1][i] != -1){
                par[lg][i]=par[lg-1][par[lg-1][i]];
            }
        }
    }
    int u, v;
    for(int i = 0 ; i < n; i ++ ){
        upd(i, ord[i]);
    }
    int winn = -1;
    int maxi = -1;
    int cur_cnt;
    int node;
    int jump;
    for(int i = 0 ; i < n; i ++ ){
        if(i){
            upd(i - 1, ord[i]);
            upd(i, ord[i - 1]);
            swap(ord[i - 1], ord[i]);
        }
        cur_cnt = 0;
        node = i;
        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            if(par[lg][node] == -1) continue;
            jump = par[lg][node];
            if(get_high(segm[jump].fi, segm[jump].se) == ord[i]){
                node = jump;
                cur_cnt += (1 << lg);
            }
        }
        if(cur_cnt > maxi){
            winn = i;
            maxi = cur_cnt;
        }
    }
    return winn;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:115:9: warning: unused variable 'gl' [-Wunused-variable]
  115 |     int gl, gr;
      |         ^~
tournament.cpp:115:13: warning: unused variable 'gr' [-Wunused-variable]
  115 |     int gl, gr;
      |             ^~
tournament.cpp:149:9: warning: unused variable 'u' [-Wunused-variable]
  149 |     int u, v;
      |         ^
tournament.cpp:149:12: warning: unused variable 'v' [-Wunused-variable]
  149 |     int u, v;
      |            ^

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 8 ms 1436 KB Output is correct
3 Correct 3 ms 1080 KB Output is correct
4 Correct 8 ms 1520 KB Output is correct
5 Correct 7 ms 1396 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 8 ms 1456 KB Output is correct
8 Correct 8 ms 1484 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 6 ms 1484 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9052 KB Output is correct
2 Correct 235 ms 20616 KB Output is correct
3 Correct 54 ms 13528 KB Output is correct
4 Correct 231 ms 22212 KB Output is correct
5 Correct 214 ms 21560 KB Output is correct
6 Correct 94 ms 18860 KB Output is correct
7 Correct 210 ms 22240 KB Output is correct
8 Correct 222 ms 22312 KB Output is correct
9 Correct 55 ms 12860 KB Output is correct
10 Correct 66 ms 13364 KB Output is correct