| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1153654 | enzy | 마상시합 토너먼트 (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int sp[maxn], marc[maxn], qtd, at[maxn], seg[4*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){
set<pair<int,int>>caras;
for(int i=0;i<n;i++){
update1(1,0,n-1,i);
caras.insert({i,i});
comeco[i].clear(); final[i].clear();
sp[i]=at[i]=marc[i]=0;
}
vector<pair<int,pair<int,int>>>process;
for(int i=0;i<c;i++){
int l=s[i]+1, r=e[i]+1;
int cnt=l;
vector<pair<int,int>>aux;
int q=query(1,0,n-1,l);
auto f=caras.lower_bound({q,0});
while(cnt<=r){
aux.push_back(*f);
f++; cnt++;
}
int idl=aux[0].first, idr=aux.back().second;
for(auto p : aux) caras.erase(p);
caras.insert({idl,idr});
process.push_back({i,{idl,idr}});
update2(1,0,n-1,idl+1,idr); // indicar q n existe mais um comeco entre idl+1 e idr
comeco[idl].push_back(i); final[idr].push_back(i);
//cout << idl << " " << idr << endl;
}
// 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(int i=0;i<n;i++) cout << sp[i] << " ";
//cout << endl;
for(auto p : process){
int l=p.second.first, r=p.second.second, id=p.first;
if(l==0) marc[id]=sp[r];
else marc[id]=sp[r]-sp[l-1];
//cout << id << " " << marc[id] << endl;
}
int resp=0, best=0; qtd=0;
for(int i=0;i<n-1;i++){ // vou andando na pos q eu to brutando o meu cara
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){ // esse cara vai da pos i+1, para a i
for(int a : comeco[i+1]){ // tirando os caras q comecavam em i+1
marc[a]--;
if(marc[a]==0&&at[a]) qtd++;
}
for(int a : final[i]){ // adicionando os caras q terminam em i
if(!marc[a]) qtd--;
marc[a]++;
}
}
for(int a : final[i]){
at[a]--;
if(!marc[a]) qtd--;
}
}
return resp;
}
=