oj.uz

Submission #772940

# Submission time Handle Problem Language Result Execution time Memory
772940 2023-07-04T13:14:57 Z Blagoj Examination (JOI19_examination) C++17
2 / 100
 3000 ms 65780 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<ll> s[400002], sum[400002];
vector<pair<ll, ll>> v;
vector<ll> val;

void merge(int k) {
    vector<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++]);
    l = sum[k * 2], r = sum[k * 2 + 1];
    p1 = p2 = 0;
    while (p1 < l.size() && p2 < r.size()) {
        if (l[p1] <= r[p2]) sum[k].push_back(l[p1++]);
        else sum[k].push_back(r[p2++]);
    }
    while (p1 < l.size()) sum[k].push_back(l[p1++]);
    while (p2 < r.size()) sum[k].push_back(r[p2++]);
}

void build(int k, int l, int r) {
    if (l == r) {
        s[k].push_back(v[l].second);
        sum[k].push_back(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;

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][0] >= bValue) {
            if (sumValue > sum[k][sum[k].size() - 1]) return;
            int lower = lower_bound(all(sum[k]), sumValue) - sum[k].begin();
            ans += sum[k].size() - lower;
            return;
        }
    }
    if (s[k * 2][s[k * 2].size() - 1] >= bValue) query(k * 2, l, (l + r) / 2, i, j, bValue, sumValue);
    if (s[k * 2 + 1][s[k * 2 + 1].size() - 1] >= 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);
    int n, q;
    cin >> n >> q;
    v.resize(n);
    val.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        val[i] = v[i].first;
    }
    sort(all(v));
    sort(all(val));
    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:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while (p1 < l.size() && p2 < r.size()) {
      |            ~~~^~~~~~~~~~
examination.cpp:24:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while (p1 < l.size() && p2 < r.size()) {
      |                             ~~~^~~~~~~~~~
examination.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while (p1 < l.size()) s[k].push_back(l[p1++]);
      |            ~~~^~~~~~~~~~
examination.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (p2 < r.size()) s[k].push_back(r[p2++]);
      |            ~~~^~~~~~~~~~
examination.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while (p1 < l.size() && p2 < r.size()) {
      |            ~~~^~~~~~~~~~
examination.cpp:32:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while (p1 < l.size() && p2 < r.size()) {
      |                             ~~~^~~~~~~~~~
examination.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while (p1 < l.size()) sum[k].push_back(l[p1++]);
      |            ~~~^~~~~~~~~~
examination.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (p2 < r.size()) sum[k].push_back(r[p2++]);
      |            ~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19116 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 11 ms 19052 KB Output is correct
6 Correct 11 ms 19108 KB Output is correct
7 Correct 61 ms 20308 KB Output is correct
8 Correct 53 ms 20308 KB Output is correct
9 Correct 55 ms 20392 KB Output is correct
10 Correct 53 ms 20428 KB Output is correct
11 Correct 17 ms 20308 KB Output is correct
12 Correct 14 ms 20180 KB Output is correct
13 Correct 51 ms 20312 KB Output is correct
14 Correct 49 ms 20316 KB Output is correct
15 Correct 53 ms 20372 KB Output is correct
16 Correct 13 ms 20276 KB Output is correct
17 Correct 13 ms 20308 KB Output is correct
18 Correct 11 ms 20224 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 65780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 65780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19116 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 11 ms 19052 KB Output is correct
6 Correct 11 ms 19108 KB Output is correct
7 Correct 61 ms 20308 KB Output is correct
8 Correct 53 ms 20308 KB Output is correct
9 Correct 55 ms 20392 KB Output is correct
10 Correct 53 ms 20428 KB Output is correct
11 Correct 17 ms 20308 KB Output is correct
12 Correct 14 ms 20180 KB Output is correct
13 Correct 51 ms 20312 KB Output is correct
14 Correct 49 ms 20316 KB Output is correct
15 Correct 53 ms 20372 KB Output is correct
16 Correct 13 ms 20276 KB Output is correct
17 Correct 13 ms 20308 KB Output is correct
18 Correct 11 ms 20224 KB Output is correct
19 Execution timed out 3073 ms 65780 KB Time limit exceeded
20 Halted 0 ms 0 KB -