oj.uz

Submission #858529

# Submission time Handle Problem Language Result Execution time Memory
858529 2023-10-08T15:46:41 Z sleepntsheep Examination (JOI19_examination) C++17
0 / 100
 1609 ms 199948 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;


#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using iset = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define N 200005
#define ALL(x) x.begin(), x.end()

int n, q, C, ans[N];
iset t[N<<2];

void Ins(int v, int l, int r, int p, int k)
{
    if (r < p || p < l) return;
    if (l != r)
    {
        int m = (l+r)/2, vl = v+1, vr = v+(m-l+1)*2;
        Ins(vl, l, m, p, k), Ins(vr, m+1, r, p, k);
    }
    t[v].insert(make_pair(k, ++C));
}

int Qry(int v, int l, int r, int x, int y, int k)
{
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) 
    {
        int sz = t[v].size();
        if (!sz) return 0;
        return sz - t[v].order_of_key(*t[v].upper_bound(make_pair(k, 0))); 
    }
    int m = (l+r)/2, vl = v+1, vr = v+(m-l+1)*2;
    return Qry(vl, l, m, x, y, k) + Qry(vr, m+1, r, x, y, k);
}

struct qry
{
    int x, y, z, i, cx;
    bool operator<(const qry &a) const { return z > a.z; }
} b[N];

struct ppl
{
    int x, y, cx;
    bool operator<(const ppl &a) const { return x+y > a.x + a.y; }
} a[N];

void compress()
{
    vector<int> v;
    for (int i = 0; i < n; ++i) v.push_back(a[i].x);
    for (int i = 0; i < q; ++i) v.push_back(b[i].x);
    sort(ALL(v));
    v.erase(unique(ALL(v)), v.end());
    for (int i = 0; i < n; ++i) a[i].cx = lower_bound(ALL(v), a[i].x) - v.begin() + 1;
    for (int i = 0; i < q; ++i) b[i].cx = lower_bound(ALL(v), b[i].x) - v.begin() + 1;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < q; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].i = i;

    compress();
    sort(a, a+n);
    sort(b, b+q);

    int j = 0;
    for (int i = 0; i < q; ++i)
    {
        for (; j < n && a[j].x + a[j].y >= b[i].z; ++j)
            Ins(0, 1, N, a[j].cx, a[j].y);
        ans[b[i].i] = Qry(0, 1, N, b[i].cx, N, b[i].y);
    }

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

    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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