제출 #698486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698486		Half	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	178 ms	17340 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

typedef tree<
  pair<ll,ll>,
  null_type,
  less<pair<ll, ll>>,
  rb_tree_tag,
  tree_order_statistics_node_update
> ordered_pair_set;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vector<pair<bool, bool>> knt(2*N, {false, false});
  for(ll i = 0; i < N-1; ++i){
    knt[i].ff = (K[i] > R);
    knt[i+1].ss = (K[i] > R);
  }
  knt[0].ss = false;
  knt[N-1].ff = false;

  vector<vector<ll>> adj(2*N);
  ordered_pair_set rem;
  for(ll i = 0; i < N; ++i){
    rem.insert({i, i});
  }
  for(ll i = 0; i < C; ++i){
    ll pr = N+i;
    auto it = rem.find_by_order(S[i]);
    pair<ll, ll> ins = {it->first, pr};
    for(ll j = S[i]; j <= E[i]; ++j){
      adj[it->ss].pb(pr);
      adj[pr].pb(it->ss);
      knt[pr].ff = knt[pr].ff | knt[it->ss].ff;
      knt[pr].ss = knt[pr].ss | knt[it->ss].ss;
      it = rem.erase(it);
    }
    rem.insert(ins);
  }

  vector<pair<ll, ll>> sc(2*N, {0, -N-1});
  for(ll i = 0; i < N; ++i)
      sc[i] = {0, -i};
  for(ll i = N; i < 2*N; ++i){
    if(adj[i].size() == 0)
      continue;
    ll pls = 0;
    for(ll ch : adj[i]){
      if(ch > i)
        continue;
      pls += knt[ch].ss;
    }
    for(ll ch : adj[i]){
      if(ch > i)
        continue;
      pls -= knt[ch].ss;
      if(pls == 0)
        sc[i] = max(sc[i], {sc[ch].ff+1, sc[ch].ss});
      pls += knt[ch].ff;
    }
  }

  pair<ll, ll> mxsc = {-1, -N-1};
  for(ll i = 0; i < 2*N; ++i)
    mxsc = max(mxsc, sc[i]);
  return -mxsc.ss;
}

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