제출 #1153633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153633		enzy	마상시합 토너먼트 (IOI12_tournament)	C++20	0 / 100	2 ms	4932 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int seg[4*maxn], sp[maxn], marc[maxn], qtd, at[maxn];
vector<int>comeco[maxn], final[maxn];
void update1(int id, int ini, int fim, int cara){
    if(ini==fim){
        seg[id]=1;
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(cara<=mid) update1(e,ini,mid,cara);
    else update1(d,mid+1,fim,cara);
    seg[id]=seg[e]+seg[d];
}

void update2(int id, int ini, int fim, int l, int r){
    if(ini>r||fim<l) return;
    if(l<=ini&&fim<=r){
        seg[id]=0;
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    update2(e,ini,mid,l,r);
    update2(d,mid+1,fim,l,r);
}

int query(int id, int ini, int fim, int val){
    if(ini==fim) return ini;
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(seg[e]>=val) return query(e,ini,mid,val);
    else return query(d,mid+1,fim,val-seg[e]);
}

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
    for(int i=0;i<n;i++){
        update1(1,0,n-1,1);
        comeco[i].clear(); final[i].clear();
    }
    vector<pair<int,pair<int,int>>>process;
    for(int i=0;i<c;i++){
        marc[i]=0;
        int l=s[i], r=e[i];
        int idl=query(1,0,n-1,l), idr=query(1,0,n-1,r);
        update2(1,0,n-1,idl,idr);
        process.push_back({i,{idl,idr}});
        comeco[idl].push_back(i); final[idr].push_back(i);
    }
    sp[0]=0;
    // começo supondo q o meu cara começa na pos 0
    for(int i=1;i<n;i++){
        sp[i]=sp[i-1];
        if(k[i-1]>r) sp[i]++;
    }
    for(auto p : process){
        int l=p.second.first, r=p.second.second, id=p.first;
        marc[id]=sp[r]-sp[l-1];
    }
    int resp=0, best=0;
    for(int i=0;i<n-1;i++){
        for(int a : comeco[i]){
            at[a]++;
            if(!marc[a]) qtd++;
        }
        if(qtd>best){
            best=qtd;
            resp=i;
        }
        if(i==n-1) break;
        if(k[i]>r){
            for(int a : final[i+1]){
                marc[a]--;
                if(marc[a]==0&&at[a]) qtd++;
            }
            for(int a : comeco[i]){
                if(!marc[a]) qtd--;
                marc[a]++;
            }
        }
        for(int a : final[i]){
            at[a]--;
            if(!marc[a]) qtd--;
        }
    }
    return resp;
}

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