제출 #858510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858510		sleepntsheep	Examination (JOI19_examination)	C++17	0 / 100	1744 ms	162332 KiB

examination

#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<<1];

void build(int v, int l, int r)
{
    int m = (l+r)/2, vl = v+1, vr = v+(m-l+1)*2;
    if (l == r)
        ;
    else
    {
        build(vl, l, m), build(vr, m+1, r);
        for (auto x : t[vl]) t[v].insert(x);
    }
}

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) return t[v].size() - t[v].order_of_key(*t[v].lower_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));
    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-1, b[i].y);
    }
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);


    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57