Submission #881339

#	Time	Username	Problem	Language	Result	Execution time	Memory
881339		rxlfd314	Fish (IOI08_fish)	C++17	0 / 100	504 ms	28752 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;
  int mx[K] = {};
  ari2 A[N];
  vt<int> fl[K];
  FOR(i, 0, N-1) {
    cin >> A[i][0] >> A[i][1];
    fl[--A[i][1]].push_back(A[i][0]);
    chmax(mx[A[i][1]], A[i][0]);
  }
  sort(A, A+N);
  
  int ord[K];
  iota(ord, ord+K, 0);
  sort(ord, ord+K, [&](const int &a, const int &b) {
    return mx[a] < mx[b];    
  });
  
  ST st(K, M);
  int O[K];
  FOR(i, 0, K-1)
    O[ord[i]] = i, sort(all(fl[i]));
  FOR(i, 0, N-1)
    st.upd(O[A[i][1]], 1);
 
  int j = N-1, ans = 0;
  ROF(i, N-1, 0) {
    auto [v, t] = A[i];
    if (v < fl[t].back())
      continue;
    for (; ~j && A[j][0] * 2 > v; j--)
      st.upd(O[A[j][1]], -1);
    int sv = *upper_bound(all(fl[t]), v>>1);
    int r = lower_bound(mx, mx+K, sv<<1) - mx - 1;
    if (r > O[t])
      (ans += 1ll * st.qry(0, O[t]-1) * st.qry(O[t]+1, r) % M) %= M;
    (ans += st.qry(0, O[t])) %= M;
    //cout << (r > O[t] ? st.qry(0, O[t]-1) * st.qry(O[t]+1, r) : 0) + st.qry(0, O[t]) << '\n';
    st.upd(O[t], -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