oj.uz

Submission #574700

# Submission time Handle Problem Language Result Execution time Memory
574700 2022-06-09T09:32:10 Z FatihSolak Jousting tournament (IOI12_tournament) C++17
100 / 100
 130 ms 16448 KB 
#include <bits/stdc++.h>
using namespace std;
struct BIT{
    vector<int> bit;
    int n;
    BIT(int size){
        n = size + 5;
        bit.assign(n,0);
    }
    void upd(int pos,int val){
        for(++pos;pos < n;pos += pos & -pos){
            bit[pos] += val;
        }
    }
    int get(int pos){
        int ret = 0;
        for(++pos;pos > 0;pos -= pos & -pos){
            ret += bit[pos];
        }
        return ret;
    }
    int get_kth(int k){
        int pos = 0;
        for(int i = 20;i>=0;i--){
            if( (pos + (1<<i)) < n && bit[pos + (1<<i)] < k){
                k -= bit[pos + (1<<i)];
                pos += (1<<i);
            }
        }
        return pos;
    }
};
struct SegTree{
    vector<pair<int,int>> t;
    int n;
    SegTree(int size){
        n = size + 5;
        t.assign(4*n,{2e9,-2e9});
    }
    void upd(int v,int tl,int tr,int pos,pair<int,int> val){
        if(tl == tr){
            t[v] = val;
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm){
            upd(v*2,tl,tm,pos,val);
        }
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v].first = min(t[v*2].first,t[v*2+1].first);
        t[v].second = max(t[v*2].second,t[v*2+1].second);
    }
    int get(int v,int tl,int tr,pair<int,int> val){
        if(t[v].first > val.first && t[v].second < val.second){
            return -1;
        }
        if(tl == tr)
            return tl;
        int tm = (tl + tr)/2;
        int tmp = get(v*2,tl,tm,val);
        if(tmp != -1)
            return tmp;
        return get(v*2+1,tm+1,tr,val);
    }
    void upd(int pos,pair<int,int> val){
        upd(1,0,n-1,pos,val);
    }
    int get(pair<int,int> val){
        return get(1,0,n-1,val);
    }
};
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
    BIT btl(n),btr(n);
    for(int i = 0;i<n;i++){
        btl.upd(i,1);
        btr.upd(i,1);
    }

    vector<pair<int,int>> ranges;

    for(int i = 0;i<c;i++){
        ranges.push_back({btl.get_kth(s[i] + 1),btr.get_kth(e[i] + 1)});
        for(int j = 0;j<e[i]-s[i];j++){
            btl.upd(btl.get_kth(s[i] + 2),-1);
            btr.upd(btr.get_kth(s[i] + 1),-1);
        }
    }
    int ans1 = -1,ans2 = -1;
    vector<pair<int,int>> st[n + 5],nd[n + 5];
    for(int i = 0;i<c;i++){
        st[ranges[i].first].push_back({ranges[i].second,i});
        nd[ranges[i].second + 1].push_back({ranges[i].first,i});
    }
    SegTree t(c);
    BIT bt(c);
    int pl = -1,pr = -1;
    for(int i = 0;i<n;i++){
        if(i && k[i] > r)
            pl = i;
        while(pr != n && (pr < i || k[pr] < r)){
            pr++;
        }
        for(auto u:st[i]){
            t.upd(u.second,{i,u.first});
            bt.upd(u.second,1);
        }
        for(auto u:nd[i]){
            t.upd(u.second,{2e9,-2e9});
            bt.upd(u.second,-1);
        }
        int num = t.get({pl,pr+1});
        if(num == -1)num = c;
        //cout << pl << " " << pr << endl;
        if(bt.get(num-1) > ans1){
            ans1 = bt.get(num-1);
            ans2 = i;
        }
    }
    return ans2;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 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 212 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 348 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 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 1084 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 5 ms 1080 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 9 ms 1040 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6728 KB Output is correct
2 Correct 107 ms 16436 KB Output is correct
3 Correct 40 ms 7348 KB Output is correct
4 Correct 102 ms 16336 KB Output is correct
5 Correct 102 ms 15680 KB Output is correct
6 Correct 111 ms 13272 KB Output is correct
7 Correct 110 ms 16448 KB Output is correct
8 Correct 130 ms 16268 KB Output is correct
9 Correct 36 ms 6648 KB Output is correct
10 Correct 44 ms 7216 KB Output is correct