Submission #363120

#	Time	Username	Problem	Language	Result	Execution time	Memory
363120		casperwang	Jousting tournament (IOI12_tournament)	C++14	0 / 100	21 ms	5244 KiB

tournament

#include <bits/stdc++.h>
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100000;

class Seg {
  private:
    struct node {
      int mmax, pos, c;
      node() {}
      node(int v, int p) {
        mmax = v, pos = p, c = 0;
      }
    } arr[MAXN*4+5];
    bool tag[MAXN*4+5];
    void pull(int now) {
      auto &nd = arr[now];
      auto &L = arr[now*2], &R = arr[now*2+1];
      if (L.mmax > R.mmax) {
        nd = L, nd.c += R.c;
      } else {
        nd = R, nd.c += L.c;
      }
    }
    void push(int now, int len) {
      if (!tag[now]) return;
      auto &nd = arr[now];
      nd.mmax = nd.pos = -1;
      nd.c = len;
      if (len > 1) {
        tag[now*2  ] = true;
        tag[now*2+1] = true;
      }
      tag[now] = false;
    }
  public:
    void build(int now, int l, int r, vector <int> &cur) {
      if (l == r) {
        arr[now] = node(cur[l], l);
        return;
      }
      int mid = l + r >> 1;
      build(now*2  , l, mid, cur);
      build(now*2+1,mid+1,r, cur);
      pull(now);
      return;
    }
    void mdy(int ml, int mr, int now, int l, int r) {
      push(now, r-l+1);
      if (ml <= l && r <= mr) {
        tag[now] = true;
        push(now, r-l+1);
        return;
      } else if (l < mr || r < ml) return;
      int mid = l + r >> 1;
      mdy(ml, mr, now*2  , l, mid);
      mdy(ml, mr, now*2+1,mid+1,r);
      pull(now);
      return;
    }
    pii qry(int ql, int qr, int now, int l, int r) {
      push(now, r-l+1);
      if (ql <= l && r <= qr) {
        return pii(arr[now].mmax, arr[now].pos);
      } else if (l > qr || r < ql) return pii(-1, -1);
      int mid = l + r >> 1;
      pii mmax(-1, -1);
      mmax = max(mmax, qry(ql, qr, now*2  , l, mid));
      mmax = max(mmax, qry(ql, qr, now*2+1,mid+1,r));
      pull(now);
      return mmax;
    }
    int kth(int k, int now, int l, int r) {
      push(now, r-l+1);
      if (l == r) return l;
      int mid = l + r >> 1;
      int cL = (mid - l + 1) - arr[now].c;
      if (k > cL) {
        k -= cL;
        int c = kth(k, now*2+1,mid+1,r);
        pull(now);
        return c;
      } else {
        int c = kth(k, now*2  , l, mid);
        pull(now);
        return c;
      }
    }
} seg;

int solve(int id, int N, int C, int R, int *K, int *S, int *E) {
  vector <int> now;
  for (int i = 0; i+1 < N; i++) {
    if (now.size() == id) now.pb(R);
    now.pb(K[i]);
  }
  if (now.size() == id) now.pb(R);
  int cnt = 0;
  seg.build(1, 0, N-1, now);
  for (int i = 0; i < C; i++) {
    int L = seg.kth(S[i], 1, 0, N-1);
    int R = seg.kth(E[i], 1, 0, N-1);
    auto [val, pos] = seg.qry(L, R, 1, 0, N-1);
    if (val == R) cnt++;
    seg.mdy(L, pos-1, 1, 0, N-1);
    seg.mdy(pos+1, R, 1, 0, N-1);
  }
  return cnt;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  pii ans = pii(0, 0);
  for (int i = 0; i < N; i++)
    ans = max(ans, pii(solve(i, N, C, R, K, S, E), -i));
  return -ans.ss;
}

Compilation message (stderr)

tournament.cpp: In member function 'void Seg::build(int, int, int, std::vector<int>&)':
tournament.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In member function 'void Seg::mdy(int, int, int, int, int)':
tournament.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In member function 'std::pair<int, int> Seg::qry(int, int, int, int, int)':
tournament.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In member function 'int Seg::kth(int, int, int, int)':
tournament.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In function 'int solve(int, int, int, int, int*, int*, int*)':
tournament.cpp:102:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |     if (now.size() == id) now.pb(R);
      |         ~~~~~~~~~~~^~~~~
tournament.cpp:105:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   if (now.size() == id) now.pb(R);
      |       ~~~~~~~~~~~^~~~~
tournament.cpp:111:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |     auto [val, pos] = seg.qry(L, R, 1, 0, N-1);
      |          ^

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