Submission #1035196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035196		kunzaZa183	Jousting tournament (IOI12_tournament)	C++17	100 / 100	136 ms	11252 KiB

tournament

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
     tree_order_statistics_node_update>
    tin;

const int maxn = 200000;
int seg[4 * maxn];
int *arr;
void build(int curin, int curl, int curr) {
  if (curl == curr) {
    seg[curin] = arr[curl];
    return;
  }
  build(curin * 2 + 1, curl, (curl + curr) / 2),
      build(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
  seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
}
int query(int curin, int curl, int curr, int ql, int qr) {
  if (curl > qr || curr < ql) return INT_MIN;
  if (ql <= curl && curr <= qr) return seg[curin];
  return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
             query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  for (int i = 0; i < N; i++) tin.insert(make_pair(i, i));
  vector<pair<int, int>> vpii;
  for (int i = 0; i < C; i++) {
    pair<int, int> newone;
    newone.first = tin.find_by_order(S[i])->first;
    newone.second = tin.find_by_order(E[i])->second;
    for (int j = E[i]; j >= S[i]; j--) tin.erase(tin.find_by_order(j));
    tin.insert(newone);
    vpii.push_back(newone);
  }
  arr = K;
  build(0, 0, N - 2);
  int things[maxn + 1];
  for (auto [a, b] : vpii) {
    int maxi = query(0, 0, N - 2, a, b - 1);
    // cout << a << " " << b << " " << maxi << "\n";
    if (maxi < R) {
      things[a]++;
      things[b + 1]--;
    }
  }
  int cur = 0;
  int maxi = -1, maxid = -1;
  for (int i = 0; i < N; i++) {
    cur += things[i];
    if (cur > maxi) {
      maxi = cur;
      maxid = i;
    }
  }
  return maxid;
}

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