Submission #623307

#	Time	Username	Problem	Language	Result	Execution time	Memory
623307		ollel	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1094 ms	2652 KiB

tournament

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<bool> vb;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

int n, c, r;
vi k, s, e;

struct SegTree {
  int n; vector<ll> tr;

  SegTree(int N) {
    n = N;
    tr.assign(4*n, 0);
  }

  int l(int x) {return x<<1;}
  int r(int x) {return (x<<1)|1;}

  ll query(int x, int L, int R, int i, int j) {
    if (L >= i && R <= j) return tr[x];
    if (i > R || j < L) return 0;
    int mid = (L + R) / 2;
    return query(l(x), L, mid, i, j) + query(r(x), mid + 1, R, i, j);
  }

  ll query(int i, int j) {return query(1, 0, n - 1, i, j);}

  void update(int x, int L, int R, int i, ll v) {
    if (i > R || i < L) return;
    if (L == R) {
      tr[x] = v;
      return;
    }
    int mid = (L + R) / 2;
    update(l(x), L, mid, i, v);
    update(r(x), mid + 1, R, i, v);
    tr[x] = tr[l(x)] + tr[r(x)];
    return;
  }

  void update(int i, ll v) {update(1, 0, n - 1, i, v);}
};

struct UF {
  int n;
  vi p, r;
  UF(int N) {
    n = N;
    p.resize(n); rep(i,0,n) p[i] = i;
    r.assign(n, 1);
  }

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

  void join(int x, int y) {
    x = P(x); y = P(y);
    if (x == y) return;
    if (r[x] > r[y]) swap(x, y);
    p[x] = y;
    if (r[x] == r[y]) r[y]++;
  }

  bool joined(int x, int y) {
    x = P(x); y = P(y);
    return (x == y);
  }
};

int eval(int x) {
  vi nk(n);
  rep(i,0,x) nk[i] = k[i];
  nk[x] = 1;
  rep(i,x+1,n) nk[i] = k[i - 1];

  int ret = 0;
  SegTree st(n);
  rep(i,0,n) st.update(i,nk[i]);
  rep(i,0,c) {
    if (s[i] > x || e[i] < x) continue;
    if (st.query(s[i], e[i]) == 1) ret++;
    else {
      return ret;
    }
  }
  return ret;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  n = N; c = C; r = R;
  k.resize(n-1); rep(i,0,n-1) k[i] = (K[i] > r) ? 2 : 0;
  s.resize(c); e.resize(c);
  rep(i,0,c) {s[i] = S[i]; e[i] = E[i];}

  SegTree compact(n);
  rep(i,0,n) compact.update(i,0);

  rep(i,0,c) {

    // binary search start

    int low = 0, high = n + 1, mid;
    while (high - low > 1) {
      mid = (low + high) / 2;
      if (mid - compact.query(0, mid) <= s[i]) low = mid;
      else high = mid;
    }
    ll oldS = s[i];
    int newLow = low;
    rep(j,0,low) if (compact.query(j, low) >= low - j) newLow = min(newLow, j);
    s[i] = newLow;
    low = s[i]; high = n + 1;
    while (high - low > 1) {
      mid = (low + high) / 2;
      if (mid - compact.query(s[i], mid) - s[i] <= (e[i] - oldS)) low = mid;
      else high = mid;
    }
    // ll currentsi = compact.query(s[i], s[i]);
    e[i] = low;
    ll newsi = (e[i] - s[i]);
    compact.update(s[i], newsi);
  }

  int ans = 0, res = 0;
  rep(i,0,n) {
    int nres = eval(i);
    if (nres > res) {
      res = nres;
      ans = i;
    }
  }
  return ans;
}

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