Submission #959060

#	Time	Username	Problem	Language	Result	Execution time	Memory
959060		vjudge1	Jousting tournament (IOI12_tournament)	C++17	0 / 100	85 ms	124340 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 1e6+6;

//bool debug = 0;
int mx, ans, n, c, p[N], sz[N], rr[N], ll[N], seg[N*4], seg2[N*4];
pair<int, int> queries[N];
vector<int> higher, lp[N], rp[N];
set<int> st[N];

int findSet(int x) {
  return (p[x] == x ? x : p[x] = findSet(p[x]));
}

void unite(int x, int y) {
  x = findSet(x);
  y = findSet(y);

  if (x == y) return;

  if (sz[x] < sz[y]) swap(x, y);

  p[y] = x;
  sz[x] += sz[y];
  ll[x] = min(ll[x], ll[y]);
  rr[x] = max(rr[x], rr[y]);
}

void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p] = c;
    return;
  }
  int mid = (l+r) >> 1;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);
  seg[p] = min(seg[p*2], seg[p*2+1]);
}

void update(int pos, int x, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p] = x;
    return;
  }
  int mid = (l+r) >> 1;
  if (pos <= mid) update(pos, x, p*2, l, mid);
  else update(pos, x, p*2+1, mid+1, r);
  seg[p] = min(seg[p*2], seg[p*2+1]);
}

int query(int x, int y, int p=1, int l=0, int r=n-1) {
  if (x > y || y < l || r < x) return c;
  else if (x <= l && r <= y) {
    return seg[p];
  }
  int mid = (l+r) >> 1;
  return min(query(x, y, p*2, l, mid), query(x, y, p*2+1, mid+1, r));
}

void update2(int pos, int x, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg2[p] += x;
    return;
  }
  int mid = (l+r) >> 1;
  if (pos <= mid) update2(pos, x, p*2, l, mid);
  else update2(pos, x, p*2+1, mid+1, r);
  seg2[p] = seg2[p*2] + seg2[p*2+1];
}

int query2(int x, int y, int p=1, int l=0, int r=n-1) {
  if (x > y || y < l || r < x) return 0;
  else if (x <= l && r <= y) {
    //if (debug) cerr << x << " " << y << " " << l << " " << r << " " << seg2[p] << endl;
    return seg2[p];
  }
  int mid = (l+r) >> 1;
  return query2(x, y, p*2, l, mid) + query2(x, y, p*2+1, mid+1, r);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  mx = ans = 0;
  n = N;
  c = C;

  for (int i = 0; i < n; i++) {
    p[i] = i;
    sz[i] = 1;
    ll[i] = rr[i] = i;
  }

  for (int i = 0; i < n-1; i++) {
    if (K[i] > R) higher.push_back(i);
  }

  for (int i = 0; i < c; i++) {
    int x = E[i]-S[i];

    int y = S[i];
    while (x--) {
      y = rr[findSet(y)];
      unite(y, y+1);
    }

    int nwR = rr[findSet(S[i])];
    queries[i] = make_pair(S[i], nwR);
    lp[S[i]].push_back(i);
    rp[nwR].push_back(i);
    //cerr << S[i] << " " << nwR << endl;
  }

  build(); // pongo todo a c
  memset(seg2, 0, sizeof(seg2));
  for (int i = 0; i < n; i++) {
    /*
    cuantas batallas gano poniendolo en i?
    miro el mas cercano por cada lado que me gana y cojo la primera query que me toca
    y que llega mas lejos que ellos con query de minimo en rango
    */

    for (int& j : lp[i]) {
      st[i].insert(j);
      st[queries[j].second].insert(j);

      update(i, *st[i].begin());
      update(queries[j].second, *st[queries[j].second].begin());

      update2(j, 1);
    }

    auto it = lower_bound(all(higher), i);
    
    int x = (it == higher.begin() ? -1 : *prev(it));
    int y = (it == higher.end() ? n-1 : *it) + 1;

    //if (i == 4) debug = 1;
    int rd = min(query(0, x), query(y, n-1));
    int nwMx = query2(0, rd-1);// rondas con idx < rd que pasan por i
    //cerr << i << " " << rd << " " << nwMx << endl;

    if (nwMx > mx) {
      mx = nwMx;
      ans = i;
    }

    for (int& j : rp[i]) {
      st[i].erase(j);
      st[queries[j].first].erase(j);

      update(i, (st[i].empty() ? c : *st[i].begin()));
      update(queries[j].first, (st[queries[j].first].empty() ? c : *st[queries[j].first].begin()));

      update2(j, -1);
    }
  }

  return ans;
}

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