oj.uz

Submission #881057

# Submission time Handle Problem Language Result Execution time Memory
881057 2023-11-30T12:49:32 Z rxlfd314 Fish (IOI08_fish) C++17
0 / 100
 379 ms 15448 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;
  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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 132 ms 10388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 4428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 6624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 10388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7164 KB Output is correct
2 Incorrect 206 ms 11344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 10600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 12044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 10492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 13412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 304 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 379 ms 15448 KB Output isn't correct
2 Halted 0 ms 0 KB -