oj.uz

Submission #772947

# Submission time Handle Problem Language Result Execution time Memory
772947 2023-07-04T13:26:32 Z Blagoj Examination (JOI19_examination) C++17
2 / 100
 3000 ms 52776 KB 
#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

vector<pair<ll, ll>> v, s[400002];
vector<ll> val;

void merge(int k) {
    vector<pair<ll, ll>> l = s[k * 2], r = s[k * 2 + 1];
    int p1 = 0, p2 = 0;
    while (p1 < l.size() && p2 < r.size()) {
        if (l[p1] <= r[p2]) s[k].push_back(l[p1++]);
        else s[k].push_back(r[p2++]);
    }
    while (p1 < l.size()) s[k].push_back(l[p1++]);
    while (p2 < r.size()) s[k].push_back(r[p2++]);
}

void build(int k, int l, int r) {
    if (l == r) {
        s[k].push_back({v[l].second, v[l].first + v[l].second});
        return;
    }
    build(k * 2, l, (l + r) / 2);
    build(k * 2 + 1, (l + r) / 2 + 1, r);
    merge(k);
}

ll ans = 0, n, q;

void query(int k, int l, int r, int i, int j, ll bValue, ll sumValue) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        if (s[k][s[k].size() - 1].first >= bValue) {
            int lower = lower_bound(all(s[k]), make_pair(bValue, sumValue)) - s[k].begin(); 
            for (int i = lower; i < s[k].size(); i++) ans += (s[k][i].second >= sumValue);
            debug(bValue,sumValue,ans, s[k]);
        }
        return;
    }
    if (s[k * 2][s[k * 2].size() - 1].first >= bValue) query(k * 2, l, (l + r) / 2, i, j, bValue, sumValue);
    if (s[k * 2 + 1][s[k * 2 + 1].size() - 1].first >= bValue) query(k * 2 + 1, (l + r) / 2 + 1, r, i, j, bValue, sumValue);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    v.resize(n);
    val.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(all(v));
    for (int i = 0; i < n; i++) val[i] = v[i].first;
    build(1, 0, n - 1);
    while (q--) {
        ll x, y, z;
        cin >> x >> y >> z;
        if (x > val[n - 1]) {
            cout << 0 << endl;
            continue;
        }
        int lower = lower_bound(all(val), x) - val.begin();
        ans = 0;
        query(1, 0, n - 1, lower, n - 1, y, z);
        cout << ans << endl;
    }
}

Compilation message

examination.cpp: In function 'void merge(int)':
examination.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while (p1 < l.size() && p2 < r.size()) {
      |            ~~~^~~~~~~~~~
examination.cpp:23:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while (p1 < l.size() && p2 < r.size()) {
      |                             ~~~^~~~~~~~~~
examination.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (p1 < l.size()) s[k].push_back(l[p1++]);
      |            ~~~^~~~~~~~~~
examination.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while (p2 < r.size()) s[k].push_back(r[p2++]);
      |            ~~~^~~~~~~~~~
examination.cpp: In function 'void query(int, int, int, int, int, long long int, long long int)':
examination.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int i = lower; i < s[k].size(); i++) ans += (s[k][i].second >= sumValue);
      |                                 ~~^~~~~~~~~~~~~
examination.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
examination.cpp:49:13: note: in expansion of macro 'debug'
   49 |             debug(bValue,sumValue,ans, s[k]);
      |             ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9720 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 10 ms 10856 KB Output is correct
8 Correct 10 ms 10880 KB Output is correct
9 Correct 12 ms 10908 KB Output is correct
10 Correct 10 ms 10836 KB Output is correct
11 Correct 9 ms 10836 KB Output is correct
12 Correct 10 ms 10752 KB Output is correct
13 Correct 11 ms 10876 KB Output is correct
14 Correct 10 ms 10880 KB Output is correct
15 Correct 12 ms 10796 KB Output is correct
16 Correct 8 ms 10836 KB Output is correct
17 Correct 9 ms 10756 KB Output is correct
18 Correct 8 ms 10708 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 51712 KB Output is correct
2 Correct 1654 ms 52648 KB Output is correct
3 Correct 1629 ms 52728 KB Output is correct
4 Correct 1761 ms 52332 KB Output is correct
5 Correct 1681 ms 52428 KB Output is correct
6 Correct 1787 ms 51884 KB Output is correct
7 Correct 2743 ms 52708 KB Output is correct
8 Correct 2848 ms 52724 KB Output is correct
9 Execution timed out 3082 ms 52776 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 51712 KB Output is correct
2 Correct 1654 ms 52648 KB Output is correct
3 Correct 1629 ms 52728 KB Output is correct
4 Correct 1761 ms 52332 KB Output is correct
5 Correct 1681 ms 52428 KB Output is correct
6 Correct 1787 ms 51884 KB Output is correct
7 Correct 2743 ms 52708 KB Output is correct
8 Correct 2848 ms 52724 KB Output is correct
9 Execution timed out 3082 ms 52776 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9720 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 10 ms 10856 KB Output is correct
8 Correct 10 ms 10880 KB Output is correct
9 Correct 12 ms 10908 KB Output is correct
10 Correct 10 ms 10836 KB Output is correct
11 Correct 9 ms 10836 KB Output is correct
12 Correct 10 ms 10752 KB Output is correct
13 Correct 11 ms 10876 KB Output is correct
14 Correct 10 ms 10880 KB Output is correct
15 Correct 12 ms 10796 KB Output is correct
16 Correct 8 ms 10836 KB Output is correct
17 Correct 9 ms 10756 KB Output is correct
18 Correct 8 ms 10708 KB Output is correct
19 Correct 1641 ms 51712 KB Output is correct
20 Correct 1654 ms 52648 KB Output is correct
21 Correct 1629 ms 52728 KB Output is correct
22 Correct 1761 ms 52332 KB Output is correct
23 Correct 1681 ms 52428 KB Output is correct
24 Correct 1787 ms 51884 KB Output is correct
25 Correct 2743 ms 52708 KB Output is correct
26 Correct 2848 ms 52724 KB Output is correct
27 Execution timed out 3082 ms 52776 KB Time limit exceeded
28 Halted 0 ms 0 KB -