Submission #772947

#	Time	Username	Problem	Language	Result	Execution time	Memory
772947		Blagoj	Examination (JOI19_examination)	C++17	2 / 100	3082 ms	52776 KiB

examination

#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 (stderr)

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 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57