Submission #105323

#	Time	Username	Problem	Language	Result	Execution time	Memory
105323		eriksuenderhauf	Jousting tournament (IOI12_tournament)	C++11	0 / 100	181 ms	8956 KiB

tournament

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int MAXN = 2e5 + 5;
int n, BIT[MAXN], sm[MAXN], cnt[MAXN];
set<int> act;

int sum(int ind) {
  ind++;
  int ret = 0;
  while (ind > 0) {
    ret += BIT[ind];
    ind -= ind & -ind;
  }
  return ret;
}

void upd(int ind, int val) {
  ind++;
  while (ind <= n) {
    BIT[ind] += val;
    ind += ind & -ind;
  }
}

int qry(int val) {
  int lo = 0, hi = n - 1, ret = -1;
  while (lo <= hi) {
    int mi = (lo + hi) / 2;
    if (sum(mi) <= val)
      ret = mi, lo = mi + 1;
    else
      hi = mi - 1;
  }
  return ret;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  n = N;
  for (int i = 0; i < n; i++) {
    sm[i] = sm[i - 1];
    if (i < n - 1 && K[i] > R)
      sm[i]++;
  }
  for (int i = 0; i < n; i++) {
    upd(i, 1);
    act.insert(i);
  }
  for (int i = 0; i < C; i++) {
    int l = qry(S[i]) + 1, r = qry(E[i] + 1);
    vi tmp;
    for (auto it = act.find(l); it != act.end() && *it <= r; it++)
      tmp.pb(*it);
    for (int j = 0; j < tmp.size(); j++) {
      upd(tmp[j], -1);
      act.erase(tmp[j]);
    }
    upd(l, 1);
    act.insert(l);
    if (sm[l] == sm[r - 1])
      cnt[l]++, cnt[r + 1]--;
  }
  pii ret = {0, 0};
  for (int i = 0; i < n; i++) {
    cnt[i] += cnt[i - 1];
    ret = max(ret, {cnt[i], -i});
  }
  return -ret.se;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < tmp.size(); j++) {
                     ~~^~~~~~~~~~~~

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