oj.uz

Submission #881503

# Submission time Handle Problem Language Result Execution time Memory
881503 2023-12-01T10:22:46 Z rxlfd314 Fish (IOI08_fish) C++17
100 / 100
 841 ms 54096 KB 
#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);
  
  sort(mx, mx+K);
 
  int j = N-1, ans = 0;
  bool seen[K] = {};
  ROF(i, N-1, 0) {
    auto [v, t] = A[i];
    if (seen[t])
      continue;
    seen[t] = true;
    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 (O[t] < r)
      (ans += 1ll * st.qry(0, O[t]-1) * (st.qry(O[t]+1, r) + M - 1) % 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) - 1) : 0) << ' ' << st.qry(0, O[t]) << '\n';
  }
  cout << ans << '\n';
}

Compilation message

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 171 ms 12644 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5776 KB Output is correct
2 Correct 90 ms 6984 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 616 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8940 KB Output is correct
2 Correct 224 ms 13376 KB Output is correct
3 Correct 230 ms 13472 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 13744 KB Output is correct
2 Correct 202 ms 14592 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9312 KB Output is correct
2 Correct 237 ms 14348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 13784 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 16104 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 14928 KB Output is correct
2 Correct 415 ms 22100 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 23892 KB Output is correct
2 Correct 329 ms 20052 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 23172 KB Output is correct
2 Correct 399 ms 22100 KB Output is correct
3 Correct 449 ms 28604 KB Output is correct
4 Correct 408 ms 22036 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 28948 KB Output is correct
2 Correct 687 ms 53072 KB Output is correct
3 Correct 841 ms 54096 KB Output is correct
4 Correct 812 ms 45652 KB Output is correct