oj.uz

Submission #366140

# Submission time Handle Problem Language Result Execution time Memory
366140 2021-02-13T09:48:19 Z casperwang Jousting tournament (IOI12_tournament) C++14
100 / 100
 176 ms 30956 KB 
#include <bits/stdc++.h>
#define int long long
#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;
const int L = 18;
const int INF = 1e9;

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, signed *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:
    pii arr[MAXN*4+5];
    int tag[MAXN*4+5];
    inline void pull(int now) {
      arr[now] = max(arr[now*2], arr[now*2+1]);
    }
    inline void push(int now, int len) {
      if (!tag[now]) return;
      arr[now].ff += tag[now];
      if (len > 1) {
        tag[now*2  ] += tag[now];
        tag[now*2+1] += tag[now];
      }
      tag[now] = 0;
      return;
    }
  public:
    void build(int now, int l, int r) {
      if (l == r) {
        arr[now] = pii(0, -l);
        return;
      }
      int mid = l + r >> 1;
      build(now*2  , l, mid);
      build(now*2+1,mid+1,r);
      pull(now);
      return;
    }
    void mdy(int ml, int mr, int k, int now, int l, int r) {
      push(now, r-l+1);
      if (ml <= l && r <= mr) {
        tag[now] += k;
        push(now, r-l+1);
        return;
      } else if (l > mr || r < ml) return;
      int mid = l + r >> 1;
      mdy(ml, mr, k, now*2  , l, mid);
      mdy(ml, mr, k, now*2+1,mid+1,r);
      pull(now);
      return;
    }
    pii qry() {
      return arr[1];
    }
} seg;

signed GetBestPosition(signed N, signed C, signed R, signed *K, signed *S, signed *E) {
  bit.build(N);
  set <int> now;
  for (int i = 0; i < N; i++) now.insert(i);
  for (int i = 0; i < C; i++) {
    int L = bit.fndL(S[i]);
    int R = bit.fndR(E[i]);
    auto it = now.upper_bound(L);
    while (it != now.end() && *it <= R) {
      bit.mdy(*it);
      it = now.erase(it);
    }
    S[i] = L, E[i] = R;
  }
  st.build(N-1, K);
  seg.build(1, 0, N-1);
  pii ans(0, 0);
  for (int i = 0; i < C; i++) {
    if (st.qry(S[i], E[i]-1) <= R) {
      seg.mdy(S[i], E[i], 1, 1, 0, N-1);
    } else {
      seg.mdy(S[i], E[i], -INF, 1, 0, N-1);
    }
    ans = max(ans, seg.qry());
  }
  return -ans.ss;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct
4 Correct 4 ms 6636 KB Output is correct
5 Correct 4 ms 6764 KB Output is correct
6 Correct 4 ms 6636 KB Output is correct
7 Correct 4 ms 6636 KB Output is correct
8 Correct 4 ms 6636 KB Output is correct
9 Correct 4 ms 6636 KB Output is correct
10 Correct 4 ms 6636 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6764 KB Output is correct
2 Correct 9 ms 7788 KB Output is correct
3 Correct 6 ms 7680 KB Output is correct
4 Correct 10 ms 7788 KB Output is correct
5 Correct 9 ms 7660 KB Output is correct
6 Correct 9 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 6 ms 7660 KB Output is correct
10 Correct 10 ms 7788 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17900 KB Output is correct
2 Correct 176 ms 29320 KB Output is correct
3 Correct 75 ms 27500 KB Output is correct
4 Correct 162 ms 30956 KB Output is correct
5 Correct 161 ms 30188 KB Output is correct
6 Correct 163 ms 30336 KB Output is correct
7 Correct 163 ms 30956 KB Output is correct
8 Correct 170 ms 30956 KB Output is correct
9 Correct 72 ms 27244 KB Output is correct
10 Correct 80 ms 29292 KB Output is correct