Submission #987530

#	Time	Username	Problem	Language	Result	Execution time	Memory
987530		huutuan	Jousting tournament (IOI12_tournament)	C++14	100 / 100	175 ms	21292 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;

template<class T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
   ordered_set<pair<int, int>> st;
   for (int i=0; i<N; ++i) st.insert({i, i});
   vector<pair<int, int>> v;
   vector<vector<int>> vl(N), vr(N);
   for (int i=0; i<C; ++i){
      int l=S[i], r=E[i];
      auto it=st.find_by_order(l);
      int x=it->first, y=-1;
      int cnt=r-l+1;
      while (cnt--){
         y=it->second;
         it=st.erase(it);
      }
      st.insert({x, y});
      v.emplace_back(x, y);
      vl[x].push_back(y);
      vr[y].push_back(x);
   }
   int LG=32-__builtin_clz(N-1);
   vector<vector<int>> sp(LG, vector<int>(N-1));
   for (int i=0; i<N-1; ++i) sp[0][i]=K[i];
   for (int k=1; k<LG; ++k) for (int i=0; i+(1<<k)-1<N-1; ++i) sp[k][i]=max(sp[k-1][i], sp[k-1][i+(1<<(k-1))]);
   auto query=[&](int l, int r) -> int {
      int lg=__lg(r-l+1);
      return max(sp[lg][l], sp[lg][r-(1<<lg)+1]);
   };
   pair<int, int> ans={-1, -1};
   int cur=0;
   for (int i=0; i<N; ++i){
      for (int j:vl[i]){
         cur+=query(i, j-1)<R;
      }
      ans=max(ans, {cur, -i});
      for (int j:vr[i]){
         cur-=query(j, i-1)<R;
      }
   }
   return -ans.second;
}

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