oj.uz

Submission #1035196

# Submission time Handle Problem Language Result Execution time Memory
1035196 2024-07-26T06:18:27 Z kunzaZa183 Jousting tournament (IOI12_tournament) C++17
100 / 100
 136 ms 11252 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 4 ms 1656 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct
7 Correct 4 ms 1572 KB Output is correct
8 Correct 4 ms 1628 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 6 ms 1624 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6092 KB Output is correct
2 Correct 123 ms 11252 KB Output is correct
3 Correct 71 ms 9552 KB Output is correct
4 Correct 124 ms 11208 KB Output is correct
5 Correct 117 ms 10960 KB Output is correct
6 Correct 124 ms 11180 KB Output is correct
7 Correct 136 ms 11212 KB Output is correct
8 Correct 127 ms 11216 KB Output is correct
9 Correct 60 ms 9388 KB Output is correct
10 Correct 76 ms 9556 KB Output is correct