Submission #890448

#	Time	Username	Problem	Language	Result	Execution time	Memory
890448		abczz	Jousting tournament (IOI12_tournament)	C++14	0 / 100	21 ms	9320 KiB

tournament

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

ll n, x, y, p = -1, f, st[400000], lazy[400000], bit[100001];
vector <array<ll, 2>> V, Q;
array<ll, 2> A[100000];
vector <ll> U;

void add(ll u, ll v) {
  while (u <= n) {
    bit[u] += v;
    u += u & -u;
  }
}
ll get(ll u) {
  ll res = 0;
  while (u) {
    res += bit[u];
    u -= u & -u;
  }
  return res;
}
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);
}
ll query(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 query(id*2, l, mid, k);
  else return max(mid, query(id*2, 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<C; ++i) {
    x = query(1, 0, n-1, S[i]);
    y = query(1, 0, n-1, E[i]);
    if (x != y) update(1, 0, n-1, x+1, y);
    V.push_back({x, y});
  }
  for (int i=0; i<n; ++i) {
    if (K[i] > R) {
      Q.push_back({p+1, i});
      p = i;
    }
  }
  sort(V.begin(), V.end(), [](auto a, auto b) {
    return a[0] > b[0];
  });
  sort(Q.begin(), Q.end(), [](auto a, auto b) {
    return a[0] > b[0];
  });
  int i=0, j=0;
  while (i < V.size() && j < Q.size()) {
    if (V[i][0] >= Q[j][0]) {
      add(V[i][1]+1, 1);
      ++i;
    }
    else {
      f = max(f, get(Q[j][1]+1));
      ++j;
    }
  }
  while (j < Q.size()) {
    f = max(f, get(Q[j][1]+1));
    ++j;
  }
  return f;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:90:12: 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]
   90 |   while (i < V.size() && j < Q.size()) {
      |          ~~^~~~~~~~~~
tournament.cpp:90:28: 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]
   90 |   while (i < V.size() && j < Q.size()) {
      |                          ~~^~~~~~~~~~
tournament.cpp:100:12: 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]
  100 |   while (j < Q.size()) {
      |          ~~^~~~~~~~~~

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