Submission #881057

#	Time	Username	Problem	Language	Result	Execution time	Memory
881057		rxlfd314	Fish (IOI08_fish)	C++17	0 / 100	379 ms	15448 KiB

fish

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = a > (b) ? a : (b))
#define chmin(a, b) (a = a < (b) ? a : (b))

struct ST {
  vt<int> st;
  const int MOD;
  ST(int n, int mod) : st(vt<int>(n<<2, 1)), MOD(mod) {}
  #define lc i << 1
  #define rc i << 1 | 1
  void upd(int p, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (tl == tr)
      st[i] += v;
    else {
      int tm = tl + tr >> 1;
      p > tm ? upd(p, v, rc, tm+1, tr) : upd(p, v, lc, tl, tm);
      st[i] = 1ll * st[lc] * st[rc] % MOD;
    }
  }
  int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (tl > qr || tr < ql)
      return 1;
    if (ql <= tl && tr <= qr)
      return st[i];
    int tm = tl + tr >> 1;
    return 1ll * qry(ql, qr, lc, tl, tm) * qry(ql, qr, rc, tm+1, tr) % MOD;
  }
  #undef lc
  #undef rc
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, K, M;
  cin >> N >> K >> M;
  ari2 A[N];
  ST st(K, M);
  FOR(i, 0, N-1) {
    cin >> A[i][0] >> A[i][1];
    st.upd(--A[i][1], 1);
  }
  sort(A, A+N);
  bool seen[K] = {};
  int j = N-1, ans = 0;
  ROF(i, N-1, 0) {
    if (seen[A[i][1]])
      continue;
    for (; ~j && A[j][0] * 2 > A[i][0]; j--)
      st.upd(A[j][1], -!seen[A[j][1]]);
    seen[A[i][1]] = true;
    (ans += st.qry(0, K-1)) %= M;
    //cout << A[i][1] << ": " << st.qry(0, K-1) << '\n';
    st.upd(A[i][1], 1 - st.qry(A[i][1], A[i][1]));
  }
  cout << ans << '\n';
}

Compilation message (stderr)

fish.cpp: In member function 'void ST::upd(int, int, int, int, int)':
fish.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
fish.cpp: In member function 'int ST::qry(int, int, int, int, int)':
fish.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5