oj.uz

Submission #1086870

# Submission time Handle Problem Language Result Execution time Memory
1086870 2024-09-11T15:55:42 Z djs100201 Fish (IOI08_fish) C++17
0 / 100
 183 ms 65536 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 5e5 + 10, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll mod1;
class seg {
   public:
    vector<ll> tree;
    ll base;
    seg(int n) {
        n++;
        for (base = 1; base <= n; base *= 2);
        tree.resize(n * 4);
        for (int i = 0; i < tree.size(); i++) tree[i] = 1;
    }
    ll f(ll l, ll r) {
        ll ret = 1;
        l += base, r += base;
        while (l <= r) {
            if (l % 2) ret = (ret * tree[l++]) % mod1;
            if (!(r % 2)) ret = (ret * tree[r--]) % mod1;
            l /= 2, r /= 2;
        }
        return ret;
    }
    void update(ll i, ll v) {
        i += base;
        tree[i] += v;
        i /= 2;
        while (i) {
            tree[i] = (tree[i * 2] * tree[i * 2 + 1]) % mod1;
            i /= 2;
        }
    }
};
vector<ll> color[n_];
void solve() {
    cin >> n >> k >> mod1;
    vector<P> v(n), I;
    vector<ll> cnt(n + 1), checked(n + 1), F(n + 1), A;
    seg ST(n + 1), ST2(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        cnt[v[i].second]++;
    }
    sort(all(v), greater<>());
    for (auto [a, b] : v) {
        if (checked[b]) {
            color[k - 1 - F[b]].push_back(a);
            continue;
        }
        checked[b] = true;
        F[b] = I.size();
        color[k - 1 - F[b]].push_back(a);
        I.push_back({a, k - 1 - F[b]});
    }
    for (int i = 0; i < n_; i++) sort(all(color[i]));
    sort(all(I));
    ll idx = 0;
    reverse(all(v));
    for (auto [a, b] : I) {
        A.push_back(a);
        while (idx < v.size() && v[idx].first * 2 <= a) {
            ST.update(F[v[idx].second], 1);
            idx++;
        }
        ans = (ans + ST.f(0, b)) % mod1;
    }
    idx = 0;
    ll idx2 = 0;
    for (auto [a, b] : I) {
        while (idx < v.size() && v[idx].first * 2 <= a) {
            ST2.update(F[v[idx].second], 1);
            idx++;
        }
        x = *upper_bound(all(color[b]), a / 2);
        auto it = lower_bound(all(A), x * 2);
        it--;
        idx2 = it - A.begin();
        ll temp = ST2.f(0, b - 1);
        temp = (temp * (ST2.f(b + 1, I[idx2 - 1].second)-1)) % mod1;

        //cout << a << ' ' << b << ' ' << x<<' '<<idx << ' ' << idx2 << ' ' << ' ' << temp << endl;
        ans += temp;
        ans %= mod1;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> tc;
    while (tc--) solve();
};

Compilation message

fish.cpp: In constructor 'seg::seg(int)':
fish.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < tree.size(); i++) tree[i] = 1;
      |                         ~~^~~~~~~~~~~~~
fish.cpp: In function 'void solve()':
fish.cpp:67:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while (idx < v.size() && v[idx].first * 2 <= a) {
      |                ~~~~^~~~~~~~~~
fish.cpp:76:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (idx < v.size() && v[idx].first * 2 <= a) {
      |                ~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12376 KB Output is correct
2 Runtime error 146 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -