제출 #1158946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158946		Sofiatpc	마상시합 토너먼트 (IOI12_tournament)	C++20	0 / 100	0 ms	320 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
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;
int v[MAXN*2], id[MAXN*2], ans[MAXN*2], r[MAXN*2], mn[MAXN*2];

int GetBestPosition(int n, int c, int R, int *K, int *s, int *e) {
  for(int i = 0; i < n-1; i++)v[i] = K[i] > R;

  ordered_set st;
  for(int i = 0; i < n; i++){
    if(v[i] == 1)id[i] = i;
    mn[i] = i;
    r[i] = i;
    st.insert({i,i});
  }

  int novo = n, resp = 0, idresp = 0;
  for(int i = 0; i < c; i++){
    int x = e[i]-s[i], l;
    mn[novo] = n+1;
    for(int j = 0; j <= x; j++){
      auto it = st.find_by_order(s[i]);
      if(j == 0)l = it->fi;
      v[novo] += v[it->sc];
      id[novo] += id[it->sc];
      r[novo] = max(r[novo],r[it->sc]);
      
      if(ans[novo] < ans[it->sc]){
        ans[novo] = ans[it->sc];
        mn[novo] = mn[it->sc];
      }else if(ans[novo] == ans[it->sc])mn[novo] = min(mn[novo],mn[it->sc]);

      st.erase(it);
    }
    st.insert({l, novo});

    if(v[novo] > 1 || (v[id[novo]] == 1 && id[novo] != r[novo])){ans[novo] = 0;}
    else{
      ans[novo]++;
      if(resp < ans[novo]){
        resp = ans[novo];
        idresp = mn[novo];
      }
    }

    novo++;
  }

  return idresp;
}

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