oj.uz

Submission #945729

# Submission time Handle Problem Language Result Execution time Memory
945729 2024-03-14T06:48:48 Z salmon Jousting tournament (IOI12_tournament) C++14
100 / 100
 89 ms 29704 KB 
#include <bits/stdc++.h>
using namespace std;

struct node{

    int s,e,m;
    int s1,e1;
    node *l,*r;
    int num;

    node(int S,int E){
        s = S;
        e = E;
        m = (s + e)/2;

        if(s == e){
            s1 = s;
            e1 = e;
            num = 1;
        }
        else{
            l = new node(s,m);
            r = new node(m + 1,e);

            num = l -> num + r -> num;
        }
    }

    pair<pair<int,int>,int> query(int k){
        if(s == e){
            return {{s1,e1},s};
        }

        if(k > l -> num){
            k -= l -> num;
            return r -> query(k);
        }
        else{
            return l -> query(k);
        }
    }

    void deactivate(int i){
        if(s == e){
            num--;
            return;
        }

        num--;

        if(i <= m) l -> deactivate(i);
        else r -> deactivate(i);
    }

    void update(int S, int E, int i){
        if(s == e){
            s1 = S;
            e1 = E;
            return;
        }

        if(i <= m) l -> update(S,E,i);
        else r -> update(S,E,i);
    }
}*root;

struct lode{

    int s, e, m;
    lode *l, *r;
    int lazy = 0;
    int v;

    lode(int S, int E){
        s = S;
        e = E;
        m = (s + e)/2;
        lazy = 0;

        if(s != e){
            l = new lode(s,m);
            r = new lode(m + 1, e);
            v = 0;
        }
        else{
            v = 0;
        }
    }

    void update(int S, int E, int k){
        if(S <= s && e <= E){
            v += k;
            lazy += k;
            return;
        }

        if(S <= m) l -> update(S,E,k);
        if(m < E) r -> update(S,E,k);

        v = lazy + l -> v + r -> v;
    }

    int query(int i){
        if(s == e) return v;

        if(i <= m) return l -> query(i) + lazy;
        else return r -> query(i) + lazy;
    }

}*loot;

int rg[100100];
int prefix[100100];
vector<int> events[100100];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    for(int i = 0; i < N - 1; i++){
        if(K[i] > R) K[i] = 1;
        else K[i] = 0;
    }

    root = new node(0,N-1);

    for(int i = 0; i < C; i++){
        int ns,ne;
        ns = 1100100100;
        ne = -1;
        int pompf;

        for(int j = 0; j <= E[i] - S[i]; j++){
            pair<pair<int,int>,int> iii = root -> query(S[i] + 1);
            ns = min(ns,iii.first.first);
            ne = max(ne,iii.first.second);

            if(j != E[i] - S[i]) root -> deactivate(iii.second);
            else{
                root -> update(ns,ne,iii.second);
            }
        }

        S[i] = ns;
        E[i] = ne;

    }


    prefix[0] = 0;

    for(int i = 1; i < N; i++){
        prefix[i] = prefix[i - 1] + K[i - 1];
    }

    for(int i = 0; i < C; i++){
        if(S[i] > 0) rg[i] = prefix[E[i]] - prefix[S[i] - 1];
        else rg[i] = prefix[E[i]];
    }

    loot = new lode(0, N - 1);

    for(int i = 0; i < C; i++){
        if(rg[i] == 0) loot -> update(S[i],E[i],1);

        events[S[i]].push_back(i);
        events[E[i] + 1].push_back(i);
    }

    pair<int,int> ans = {-1,-1};

    for(int i = 0; i < N; i++){
        if(i == 0){
            ans = max(ans,{loot -> query(i),-i});
            continue;
        }

        if(K[i - 1] == 1){
            for(int j : events[i]){
                if(S[j] == i){
                    rg[j]--;
                    if(rg[j] == 0){
                        loot -> update(S[j],E[j],1);
                    }
                }
                else{
                    rg[j]++;
                    if(rg[j] == 1){
                        loot -> update(S[j],E[j],-1);
                    }
                }
            }
        }
        ans = max(ans,{loot -> query(i),-i});
    }

    return -ans.second;

}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:129:13: warning: unused variable 'pompf' [-Wunused-variable]
  129 |         int pompf;
      |             ^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2744 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2848 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 4 ms 3932 KB Output is correct
3 Correct 3 ms 3932 KB Output is correct
4 Correct 4 ms 3932 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 5 ms 3932 KB Output is correct
7 Correct 5 ms 4036 KB Output is correct
8 Correct 4 ms 3928 KB Output is correct
9 Correct 3 ms 3928 KB Output is correct
10 Correct 6 ms 3932 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15408 KB Output is correct
2 Correct 77 ms 29704 KB Output is correct
3 Correct 44 ms 25684 KB Output is correct
4 Correct 79 ms 29616 KB Output is correct
5 Correct 77 ms 28496 KB Output is correct
6 Correct 89 ms 27980 KB Output is correct
7 Correct 80 ms 29676 KB Output is correct
8 Correct 81 ms 29572 KB Output is correct
9 Correct 40 ms 25424 KB Output is correct
10 Correct 45 ms 25808 KB Output is correct