oj.uz

Submission #905328

# Submission time Handle Problem Language Result Execution time Memory
905328 2024-01-13T01:46:38 Z juliany2 Examination (JOI19_examination) C++17
0 / 100
 625 ms 13604 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct BIT {
    int n;
    vector<T> bit;

    void init(int sz) { bit = vector<T> (n = sz + 7); }

    void upd(int i, T x) { 
        for (i++; i < n; i += i & -i) bit[i] += x;
    }

    T query(int i) {
        T ret = 0;
        for (i++; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    }

    T query(int l, int r) { return query(r) - query(l - 1); };
};

const int N = 1e5 + 7, B = 330;
int n, q;
array<int, 2> a[N];
vector<array<int, 3>> p[N];
int pos[N], pos2[N], ans[N];
BIT<int> bit[B];
vector<int> srt[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> q;

    for (int i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1];

    sort(a, a + n, greater<>());

    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int x, int y) { return a[x][1] > a[y][1]; });

    for (int i = 0; i < n; i++)
        pos[ord[i]] = i;

    for (int l = 0; l < n; l += B) {
        int b = l / B;
        bit[b].init(B);
        for (int i = l; i < min(l + B, n); i++)
            srt[b].push_back(ord[i]);

        sort(all(srt[b]), [&](int x, int y) { return a[x][0] + a[x][1] > a[y][0] + a[y][1]; });

        for (int i = 0; i < srt[b].size(); i++)
            pos2[srt[b][i]] = i;
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;

        if (x <= a[0][0]) {
            array<int, 2> cur = {x, INT_MAX};
            int j = upper_bound(a, a + n, cur, greater<>()) - a - 1;
            p[j].push_back({y, z, i});
        }
    }

    auto process = [&](int b, int z) {
        int lo = 0, hi = srt[b].size() - 1, r = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;

            int idx = srt[b][mid];
            if (a[idx][0] + a[idx][1] >= z)
                r = mid, lo = mid + 1;
            else
                hi = mid - 1;
        }

        return (r >= 0 ? bit[b].query(0, r) : 0);
    };

    for (int i = 0; i < n; i++) {
        bit[pos[i] / B].upd(pos2[i], 1);

        for (auto &[y, z, j] : p[i]) {
            int p = 0;
            while (p < n && a[ord[p]][1] >= y) {
                if (p % B == 0 && p + B - 1 < n && a[ord[p + B - 1]][1] >= y) {
                    ans[j] += process(p / B, z);
                    p += B;
                }
                else {
                    ans[j] += ord[p] <= i && a[ord[p]][0] + a[ord[p]][1] >= z;
                    p++;
                }
            }
        }
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 0; i < srt[b].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 7 ms 7052 KB Output is correct
8 Correct 7 ms 7016 KB Output is correct
9 Correct 7 ms 7004 KB Output is correct
10 Correct 6 ms 6824 KB Output is correct
11 Incorrect 7 ms 7004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 7 ms 7052 KB Output is correct
8 Correct 7 ms 7016 KB Output is correct
9 Correct 7 ms 7004 KB Output is correct
10 Correct 6 ms 6824 KB Output is correct
11 Incorrect 7 ms 7004 KB Output isn't correct
12 Halted 0 ms 0 KB -