oj.uz

Submission #216202

# Submission time Handle Problem Language Result Execution time Memory
216202 2020-03-26T21:39:23 Z DS007 Examination (JOI19_examination) C++14
0 / 100
 3000 ms 164472 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mid (l + r) / 2
#define child v * 2
#define index_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>

struct query {
    int x, y, z, i, ans;

    query() {
        x = y = z = i = ans = -1;
    }
};

const int N = 1e5 + 5;
int a[N], b[N];
pair<int, int> s[N];
query qry[N];
int n, q;

index_set t[N * 4];
multimap<int, int> m;

void build(int v, int l, int r) {
    if (l == r) {
        t[v].insert({0, l});
        return;
    }

    build(child, l, mid);
    build(child + 1, mid + 1, r);

    for (auto &i : t[child])
        t[v].insert(i);
    for (auto &i : t[child + 1])
        t[v].insert(i);
}

pair<int, int> update(int v, int l, int r, int tl, int val) {
    if (l == r && l == tl) {
        auto temp = *t[v].begin();
        t[v].clear();
        t[v].insert({val, tl});
        return temp;
    }

    pair<int, int> ret = tl <= mid ? update(child, l, mid, tl, val) : update(child + 1, mid + 1, r, tl, val);
    t[v].erase(ret);
    t[v].insert({val, tl});
    return ret;
}

int query(int v, int l, int r, int tl, int tr, int val) {
    if (tl > tr)
        return 0;
    else if (l == tl && r == tr)
        return t[v].size() - t[v].order_of_key({val, -1});
    return query(child, l, mid, tl, min(mid, tr), val) + query(child + 1, mid + 1, r, max(mid + 1, tl), tr, val);
}

void solveTestCase() {
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> s[i].first >> s[i].second, a[i] = s[i].first, b[i] = s[i].second;
    for (int i = 0; i < q; i++)
        cin >> qry[i].x >> qry[i].y >> qry[i].z, qry[i].i = i;

    build(1, 0, n - 1);
    sort(a, a + n, greater<>());
    sort(b, b + n);
    sort(s, s + n, greater<>());

    sort(qry, qry + q, [](auto &q1, auto &q2) {
        return q1.x > q2.x;
    });

    for (int i = 0; i < n; i++)
        m.insert({b[i], i});

    for (int i = 0, p = 0; i < q; i++) {
        while (p != n && s[p].first >= qry[i].x) {
            auto itr = m.find(s[p].second);
            update(1, 0, n - 1, itr->second, s[p].first + s[p].second);
            m.erase(itr);
            p++;
        }

        int tl = lower_bound(b, b + n, qry[i].y) - b;
        qry[i].ans = query(1, 0, n - 1, tl, n - 1, qry[i].z);
    }

    sort(qry, qry + q, [](auto &q1, auto &q2) {
        return q1.i < q2.i;
    });

    for (int i = 0; i < q; i++)
        cout << qry[i].ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41848 KB Output is correct
2 Correct 42 ms 41856 KB Output is correct
3 Correct 44 ms 41976 KB Output is correct
4 Correct 49 ms 41848 KB Output is correct
5 Correct 43 ms 41848 KB Output is correct
6 Correct 49 ms 41848 KB Output is correct
7 Correct 70 ms 44664 KB Output is correct
8 Correct 68 ms 44704 KB Output is correct
9 Correct 75 ms 44664 KB Output is correct
10 Correct 62 ms 44664 KB Output is correct
11 Correct 80 ms 44664 KB Output is correct
12 Incorrect 63 ms 44536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3096 ms 164472 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 3096 ms 164472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41848 KB Output is correct
2 Correct 42 ms 41856 KB Output is correct
3 Correct 44 ms 41976 KB Output is correct
4 Correct 49 ms 41848 KB Output is correct
5 Correct 43 ms 41848 KB Output is correct
6 Correct 49 ms 41848 KB Output is correct
7 Correct 70 ms 44664 KB Output is correct
8 Correct 68 ms 44704 KB Output is correct
9 Correct 75 ms 44664 KB Output is correct
10 Correct 62 ms 44664 KB Output is correct
11 Correct 80 ms 44664 KB Output is correct
12 Incorrect 63 ms 44536 KB Output isn't correct
13 Halted 0 ms 0 KB -