oj.uz

Submission #881345

# Submission time Handle Problem Language Result Execution time Memory
881345 2023-12-01T07:12:38 Z rxlfd314 Fish (IOI08_fish) C++17
0 / 100
 548 ms 25168 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);
 
  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 - 1) %= 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
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 456 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 344 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 1 ms 348 KB Output is correct
2 Incorrect 163 ms 10196 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 76 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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