제출 #1154386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154386		Sofiatpc	Jousting tournament (IOI12_tournament)	C++20	0 / 100	0 ms	324 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define sc second
#define sz(v) (int)v.size()
typedef pair<int,int> pii;
typedef tree< pii, null_type, less<pii>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int MAXN = 1e5+5, MAX = 17;
int sparse[2*MAXN][MAX+5], seg[MAXN*4], v[MAXN];
vector<int> vl,vr;
ordered_set st;

void build(int node, int l, int r){
  if(l == r){
    seg[node] = v[l];
    return;
  }

  int mid = (l+r)/2, e = node*2, d = node*2+1;
  build(e,l,mid); build(d,mid+1,r);

  seg[node] = max(seg[e],seg[d]);
}

void update(int node, int l, int r, int i, int x){
  if(i < l || r < i)return;
  if(l == r){
    seg[node] = x;
    return;
  }

  int mid = (l+r)/2, e = node*2, d = node*2+1;
  update(e,l,mid,i,x); update(d,mid+1,r,i,x);

  seg[node] = max(seg[e],seg[d]);
}

int query(int node, int l, int r, int i, int j){
  if(j < l || r < i)return 0;
  if(i <= l && r <= j)return seg[node];
  
  int mid = (l+r)/2, e = node*2, d = node*2+1;
  return max(query(e,l,mid,i,j), query(d,mid+1,r,i,j));
}

int GetBestPosition(int n, int c, int r, int *K, int *s, int *e) {
  for(int i = 0; i < n; i++){
    st.insert({i,i});
    vl.push_back(i); vr.push_back(i);
    if(i != n-1)v[i+1] = K[i];
  }
  v[0] = r;

  build(1,0,n-1);

  for(int i = 0; i < 2*n; i++)
    for(int j = 0; j <= MAX; j++)sparse[i][j] = -1;

  int novo = n;
  for(int i = 0; i < c; i++){
    int x = e[i]-s[i];

    for(int j = 0; j <= x; j++){
      auto it = st.find_by_order(s[i]);

      if(j == 0)vl.push_back(it->fi);
      if(j == x)vr.push_back(vr[it->sc]);

      sparse[it->sc][0] = novo;
      st.erase(it);
    }
    st.insert({vl[novo], novo});
    novo++;
  }

  for(int j = 1; j <= 1; j++)
    for(int i = 0; i < sz(vl); i++)
      if(sparse[i][j-1] != -1)
        sparse[i][j] = sparse[sparse[i][j-1]][j-1];
      

  int ans = 0, pos = 0;
  for(int i = 0; i < n; i++){
    if(i != 0){
      swap(v[i-1],v[i]);
      update(1,0,n-1, i-1, v[i-1]);
      update(1,0,n-1, i, v[i]);
    }

    int cur = i, qtd = 0;
    for(int j = MAX; j >= 0; j--){
      if(sparse[cur][j] == -1)continue;
      int mx = query(1,0,n-1, vl[sparse[cur][j]], vr[sparse[cur][j]]);
      if(mx == r){
        qtd += (1<<j);
        cur = sparse[cur][j];
      }
    }
    if(ans < qtd){ans = qtd; pos = i;}
    else if(ans == qtd && pos > i)pos = i;
  }

  return pos;
}

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