oj.uz

Submission #890539

# Submission time Handle Problem Language Result Execution time Memory
890539 2023-12-21T12:31:36 Z abczz Jousting tournament (IOI12_tournament) C++14
100 / 100
 68 ms 12332 KB 
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

ll n, x, y, p = -1, s, f, tmp, id = 0, st[400000], lazy[400000];
vector <array<ll, 2>> V;
vector <ll> U;
array<ll, 2> A[100000];

void push(ll id) {
  if (lazy[id]) {
    st[id*2] = st[id*2+1] = 0;
    lazy[id*2] = lazy[id*2+1] = 1;
    lazy[id] = 0;
  }
}
void update(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql) return;
  else if (ql <= l && r <= qr) {
    st[id] = 0;
    lazy[id] = 1;
    return;
  }
  push(id);
  ll mid = (l+r)/2;
  update(id*2, l, mid, ql, qr);
  update(id*2+1, mid+1, r,  ql, qr);
  st[id] = st[id*2] + st[id*2+1];
}
ll queryL(ll id, ll l, ll r, ll k) {
  if (l == r) return l;
  push(id);
  ll mid = (l+r)/2;
  if (st[id*2] >= k) return queryL(id*2, l, mid, k);
  else return queryL(id*2+1, mid+1, r, k-st[id*2]);
}
ll queryR(ll id, ll l, ll r, ll k) {
  if (l == r) {
    if (st[id] == k) return l;
    else return -1e18;
  }
  push(id);
  ll mid = (l+r)/2;
  if (st[id*2] > k) return queryR(id*2, l, mid, k);
  else return max(mid, queryR(id*2+1, mid+1, r, k-st[id*2]));
}
void build(ll id, ll l, ll r) {
  if (l == r) {
    st[id] = 1;
    return;
  }
  ll mid = (l+r)/2;
  build(id*2, l, mid);
  build(id*2+1, mid+1, r);
  st[id] = st[id*2] + st[id*2+1];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  n = N;
  build(1, 0, n-1);
  for (int i=0; i<n-1; ++i) {
    if (K[i] > R) {
      U.push_back(i);
    }
  }
  for (int i=0; i<C; ++i) {
    ++S[i], ++E[i];
    x = queryL(1, 0, n-1, S[i]);
    y = queryR(1, 0, n-1, E[i]);
    if (x != y) update(1, 0, n-1, x+1, y);
    auto it = lower_bound(U.begin(), U.end(), x);
    if (it == U.end() || *it+1 > y) {
      V.push_back({x, 1});
      V.push_back({y+1, -1});
    }
  }
  sort(V.begin(), V.end());
  int j=0;
  for (int i=0; i<n; ++i) {
    while (j < V.size()) {
      if (V[j][0] == i) s += V[j++][1];
      else break;
    }
    if (s > f) {
      f = s;
      id = i;
    }
  }
  return id;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while (j < V.size()) {
      |            ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4548 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 1 ms 4556 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8660 KB Output is correct
2 Correct 60 ms 11716 KB Output is correct
3 Correct 13 ms 8444 KB Output is correct
4 Correct 68 ms 11332 KB Output is correct
5 Correct 66 ms 12264 KB Output is correct
6 Correct 53 ms 10512 KB Output is correct
7 Correct 63 ms 11084 KB Output is correct
8 Correct 59 ms 12332 KB Output is correct
9 Correct 9 ms 6868 KB Output is correct
10 Correct 13 ms 7892 KB Output is correct