oj.uz

Submission #698486

# Submission time Handle Problem Language Result Execution time Memory
698486 2023-02-13T15:33:01 Z Half Jousting tournament (IOI12_tournament) C++17
100 / 100
 178 ms 17340 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 5 ms 1084 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 6 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 7 ms 1268 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8448 KB Output is correct
2 Correct 175 ms 17332 KB Output is correct
3 Correct 83 ms 15192 KB Output is correct
4 Correct 137 ms 17288 KB Output is correct
5 Correct 141 ms 16728 KB Output is correct
6 Correct 178 ms 16428 KB Output is correct
7 Correct 160 ms 17280 KB Output is correct
8 Correct 144 ms 17340 KB Output is correct
9 Correct 91 ms 15152 KB Output is correct
10 Correct 88 ms 15292 KB Output is correct