Submission #1112198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112198		lucascgar	Jousting tournament (IOI12_tournament)	C++17	100 / 100	329 ms	13248 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

/*
filas
pos L é ultima com L atrás dela
pos R também
*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 1e5+10;

void updt(vector<int> &bit, int p, int v){
    p++;
    while (p<bit.size()){
        bit[p]+=v;
        p += p&-p;
    }
}

int qry(vector<int> &bit, int p){
    p++;
    int ss = 0;
    while (p>0){
        ss += bit[p];
        p -= p&-p;
    }

    return ss;
}

int nrmr(int l, vector<int> &bit, int n){

    int in = 0, fi = n-1, me;
    // ultima com até l atras
    while (in<=fi){  // da pra deixar log ao invés de log²
        me = (in+fi)/2;

        int at = qry(bit, me-1);

        if (at<=l) in=me+1;
        else fi = me-1;

    }

    return in-1;

}

int nrml(int l, vector<int> &bit, int n){

    int in = 0, fi = n-1, me;
    // primeira com ao menos l atras
    while (in<=fi){  // da pra deixar log ao invés de log²
        me = (in+fi)/2;

        int at = qry(bit, me-1);

        if (at>=l) fi = me-1;
        else in = me+1;

    }

    return fi+1;

}
int lm;
void bseg(vector<int> &seg, int id, int il, int ir, int *K){
    if (il==ir){
        if (il==lm) seg[id]=-1;
        else seg[id] = K[il-1];
        return;
    }

    int m = (il+ir)/2;

    bseg(seg, 2*id, il, m, K);
    bseg(seg, 2*id+1, m+1, ir, K);

    seg[id] = max(seg[2*id], seg[2*id+1]);

}

int qseg(vector<int> &seg, int id, int il, int ir, int l, int r){
    if (ir<l || il>r) return -1;

    if (il>=l && ir<=r) return seg[id];
    int m = (il+ir)/2;

    return max(qseg(seg, 2*id, il,m,l,r), qseg(seg, 2*id+1, m+1, ir, l, r));

}

int GetBestPosition(int n, int c, int r, int *K, int *L, int *R){
    lm=n;
    // ajustar jousts
    vector<int> bit(n, 0);
    set<int> pr;
    for (int i=0;i<n-1;i++){
        updt(bit, i, 1);
        pr.insert(i);
    }
    vector<vector<int>> q(n+1);
    for (int i=0;i<c;i++){
        L[i] = nrml(L[i], bit, n), R[i] = nrmr(R[i], bit, n);
        // remover todo mundo menos o cara da direita
        auto it = pr.lower_bound(L[i]);
        while (it != pr.end() && *it < R[i]){
            updt(bit, *it, -1);
            pr.erase(it);
            it = pr.lower_bound(L[i]);
        }

        q[L[i]].push_back(R[i]);

    }
    vector<int> seg(4*(n+1), -1);

    bseg(seg, 1, 1, n, K);

    vector<pii> inc;  // l menores tem sempre r maiores (logo, mais à esquerda em inc veio antes)
    int pos=0, ans=-1;


    for (int i=0;i<=n-1;i++){  // botando atras de i (em i) (se alguem acaba em i ninguem começa em i)

        while (!q[i].empty()){
            inc.emplace_back(i, q[i].back()-1);
            q[i].pop_back();
        }
        
        int v = 0;


        int in = 0, fi = inc.size()-1, me;

        while (in<=fi){

            me = (in+fi)/2;

            int x = qseg(seg, 1, 1, n, inc[me].first+1, inc[me].second+1);  // maior no intervalo

            if (x<r) fi = me-1, v = inc.size()-me;
            else in = me+1;

        }
        if (v>ans){
            ans=v, pos=i;
        }

        while (!inc.empty() && inc.back().second<i) inc.pop_back();
    }

    return pos;

}
// int K[MAXN], L[MAXN], R[MAXN];
// signed main(){  // DEBUG ONLY
//     std::ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int n, c, r;
//     cin >> n >> c >> r;

//     for (int i=0;i<n-1;i++) cin >> K[i];
//     for (int i=0;i<c;i++){
//         cin >> L[i] >> R[i];
//     }

//     cout << GetBestPosition(n, c, r, K, L, R) << '\n';

//     return 0;
// }

Compilation message (stderr)

tournament.cpp: In function 'void updt(std::vector<int>&, int, int)':
tournament.cpp:19:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (p<bit.size()){
      |            ~^~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51