제출 #1237862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237862		caacrugon	Jousting tournament (IOI12_tournament)	C++20	100 / 100	47 ms	5312 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

vector<int> tree(100010*4,0);

void build(int n, int l, int r){
  if(l==r){
    tree[n]=1;
    return;
  }
  int m=l+((r-l)/2);
  build(n*2,l,m);
  build(n*2+1,m+1,r);
  tree[n]=tree[n*2]+tree[n*2+1];
  return;
}

void update(int n, int ql, int qr, int l, int r){
  if(ql>r || qr<l) return; 
  if(ql<=l && r<=qr){
    tree[n]=0;
    return;
  }
  int m=l+((r-l)/2);
  update(n*2,ql,qr,l,m);
  update(n*2+1,ql,qr,m+1,r);
  tree[n]=tree[n*2]+tree[n*2+1];
}

int query(int n, int l, int r, int x, int i){
  if(l==r)return l;
  int m=l+((r-l)/2);
  if(tree[2*n]+i>=x)return query(n*2,l,m,x,i);
  else{
    i+=tree[n*2];
    return query(n*2+1,m+1,r,x,i);
  }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int ans=0;
  vector<int> pMax(N+5,0),tmp(N+5,0),tmp2(N+5,0);
  vector<pair<int,int>> ln;
  int wins=0;
  for(int i=0;i<N-1;i++){
    if(K[i]>R){
      tmp[i+1]++;
      tmp2[i]++;
      wins++;
    }
  }
  for(int i=0;i<N;i++){
    tmp[i+1]+=tmp[i];
    tmp2[N-1-i]+=tmp2[N-i];
    ln.push_back({i,i});
  }
  build(1,0, N);
  for(int i=0;i<C;i++){
    int l=query(1,0,N,S[i]+1,0);
    int r=query(1,0,N,E[i]+2,0)-1;
    update(1,l+1,r,0,N);
    if(tmp[l]+tmp2[r]==wins){
      pMax[l]++;
      pMax[r+1]--;
    }
  }
  int mx=pMax[0],bestWins=pMax[0];
  for(int i=1;i<=N;i++){
    mx+=pMax[i];
    if(mx>bestWins){
      bestWins=mx;
      ans=i;
    }
  }
  return ans;
}

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