Submission #366126

#	Time	Username	Problem	Language	Result	Execution time	Memory
366126		casperwang	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	48 ms	6124 KiB

tournament

#include <bits/stdc++.h>
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;
const int L = 20;

class Bit {
  private:
    int arr[MAXN+1];
    int N;
    inline int lb(int a) {
      return a &- a;
    }
  public:
    void build(int n) {
      N = n;
      for (int i = 1; i <= N; i++)
        for (int j = i; j <= N; j+=lb(j))
          arr[j]++;
    }
    void mdy(int a) {
      a++;
      for (int i = a; i <= N; i+=lb(i))
        arr[i]--;
    }
    int qry(int a) {
      a++;
      int sum = 0;
      for (int i = a; i; i-=lb(i))
        sum += arr[i];
      return sum;
    }
    int fndL(int a) {
      a++;
      int now = 0, s = 0;
      for (int i = __lg(N); i >= 0; i--)
        if (now + (1<<i) <= N && s + arr[now + (1<<i)] < a)
          now += (1<<i), s += arr[now];
      return now;
    }
    int fndR(int a) {
      a++;
      int now = 0, s = 0;
      for (int i = __lg(N); i >= 0; i--) {
        if (now + (1<<i) <= N && s + arr[now + (1<<i)] <= a)
          now += (1<<i), s += arr[now];
      }
      return now-1;
    }
} bit;

class SparseTable {
  private:
    int arr[MAXN+1][L];
    int N;
  public:
    void build(int n, int *K) {
      N = n;
      for (int i = 0; i < N; i++)
        arr[i][0] = K[i];
      for (int i = 1; i < L; i++)
        for (int j = 0; j < N-(1<<i)+1; j++)
          arr[j][i] = max(arr[j][i-1], arr[j+(1<<(i-1))][i-1]);
    }
    int qry(int L, int R) {
      int k = __lg(R-L+1);
      return max(arr[L][k], arr[R-(1<<k)+1][k]);
    }
} st;

class Seg {
  private:
    int arr[MAXN*4+5];
    bool flag[MAXN*4+5];
    int tag[MAXN*4+5];
    void pull(int now) {
      arr[now] = max(arr[now*2] * flag[now*2], arr[now*2+1] * flag[now*2+1]);
      flag[now] = (flag[now*2] || flag[now*2+1]);
    }
    void push(int now, int len) {
      arr[now] += tag[now];
      if (len > 1) {
        tag[now*2  ] += tag[now];
        tag[now*2+1] += tag[now];
        if (!flag[now]) {
          flag[now*2  ] = false;
          flag[now*2+1] = false;
        }
      }
      tag[now] = 0;
    }
  public:
    void build(int now, int l, int r) {
      arr[now] = 0;
      flag[now] = true;
      if (l == r) return;
      int mid = l + r >> 1;
      build(now*2  , l, mid);
      build(now*2+1,mid+1,r);
      pull(now);
      return;
    }
    void add(int ml, int mr, int now, int l, int r) {
      push(now, r-l+1);
      if (ml <= l && r <= mr) {
        tag[now]++;
        push(now, r-l+1);
        return;
      } else if (l > mr || r < ml) return;
      int mid = l + r >> 1;
      add(ml, mr, now*2  , l, mid);
      add(ml, mr, now*2+1,mid+1,r);
      pull(now);
      return;
    }
    void stp(int ml, int mr, int now, int l, int r) {
      push(now, r-l+1);
      if (ml <= l && r <= mr) {
        flag[now] = false;
        push(now, r-l+1);
        return;
      }
      int mid = l + r >> 1;
      stp(ml, mr, now*2  , l, mid);
      stp(ml, mr, now*2+1,mid+1,r);
      pull(now);
      return;
    }
    int qry() {
      return arr[1] * flag[1];
    }
} seg;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  bit.build(N);
  for (int i = 0; i < C; i++) {
    int L = bit.fndL(S[i]);
    int R = bit.fndR(E[i]);
    for (int j = L+1; j <= R; j++)
      if (bit.qry(j) > bit.qry(j-1))
        bit.mdy(j);
    S[i] = L, E[i] = R;
  }
  st.build(N-1, K);
  seg.build(1, 0, N-1);
  int ans = 0;
  for (int i = 0; i < C; i++) {
    if (st.qry(S[i], E[i]-1) < R) {
      seg.add(S[i], E[i], 1, 0, N-1);
    } else {
      continue;
      seg.stp(S[i], E[i], 1, 0, N-1);
    }
    ans = max(ans, seg.qry());
  }
  return ans;
}

Compilation message (stderr)

tournament.cpp: In member function 'void Seg::build(int, int, int)':
tournament.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In member function 'void Seg::add(int, int, int, int, int)':
tournament.cpp:114:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |       int mid = l + r >> 1;
      |                 ~~^~~
tournament.cpp: In member function 'void Seg::stp(int, int, int, int, int)':
tournament.cpp:127:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |       int mid = l + r >> 1;
      |                 ~~^~~

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