oj.uz

Submission #987530

# Submission time Handle Problem Language Result Execution time Memory
987530 2024-05-23T01:06:36 Z huutuan Jousting tournament (IOI12_tournament) C++14
100 / 100
 175 ms 21292 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 5 ms 1112 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct
7 Correct 5 ms 1116 KB Output is correct
8 Correct 5 ms 1116 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10188 KB Output is correct
2 Correct 163 ms 19184 KB Output is correct
3 Correct 129 ms 14108 KB Output is correct
4 Correct 171 ms 21220 KB Output is correct
5 Correct 164 ms 18920 KB Output is correct
6 Correct 172 ms 21292 KB Output is correct
7 Correct 175 ms 19612 KB Output is correct
8 Correct 163 ms 19208 KB Output is correct
9 Correct 109 ms 13476 KB Output is correct
10 Correct 115 ms 19568 KB Output is correct