Submission #574700

#	Time	Username	Problem	Language	Result	Execution time	Memory
574700		FatihSolak	Jousting tournament (IOI12_tournament)	C++17	100 / 100	130 ms	16448 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51