제출 #1308792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308792		vuviet	Examination (JOI19_examination)	C++20	100 / 100	645 ms	54076 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define lb lower_bound
#define all(x) x.begin(), x.end()

constexpr int maxn = 2e5 + 5;
constexpr int inf = 1e9 + 7;
vector<int> pos[maxn], bit[maxn];
int n, m, q, result[maxn];

struct item
{
    int x, y, z, id = -1;
    bool operator < (item o) const {
        return z > o.z;
    }
} arr[maxn], qr[maxn];

void fakeget(int u, int v)
{
    for (; u > 0; u -= u & -u)
        pos[u].push_back(v);
}

void fakeupdate(int u, int v)
{
    for (; u <= m; u += u & -u)
        pos[u].push_back(v);
}

void fakequery(int x1, int y1, int x2, int y2)
{
    fakeget(x2, y2), fakeget(x2, y1 - 1);
    fakeget(x1 - 1, y2), fakeget(x1 - 1, y1 - 1);
}

void update(int u, int v, int x)
{
    for (int i = u; i <= m; i += i & -i)
    {
        int j = lb(all(pos[i]), v) - pos[i].begin() + 1;
        while (j < bit[i].size())
            bit[i][j] += x, j += j & -j;
    }
}

int get(int u, int v)
{
    int res = 0;
    for (int i = u; i > 0; i -= i & -i)
    {
        int j = lb(all(pos[i]), v) - pos[i].begin() + 1;
        while (j > 0)
            res += bit[i][j], j -= j & -j;
    }
    return res;
}

int query(int x1, int y1, int x2, int y2)
{
    if (x1 > x2 || y1 > y2) return 0;
    int res = get(x2, y2) + get(x1 - 1, y1 - 1);
    return res - get(x2, y1 - 1) - get(x1 - 1, y2);
}

void Compress()
{
    vector<int> values;
    for (int i = 1; i <= n; ++i)
        values.push_back(arr[i].x);
    for (int i = 1; i <= q; ++i)
        values.push_back(qr[i].x);
    sort(all(values));
    values.resize(unique(all(values)) - values.begin());
    for (int i = 1; i <= n; ++i)
        arr[i].x = lb(all(values), arr[i].x) - values.begin() + 1;
    for (int i = 1; i <= q; ++i)
        qr[i].x = lb(all(values), qr[i].x) - values.begin() + 1;
}

void ReadData()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    m = n + q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i].x >> arr[i].y;
        arr[i].z = arr[i].x + arr[i].y;
    }
    for (int i = 1; i <= q; ++i)
    {
        cin >> qr[i].x >> qr[i].y >> qr[i].z;
        qr[i].id = i;
    }
}

void Solve()
{
    sort(arr + 1, arr + 1 + n);
    sort(qr + 1, qr + 1 + q);
    Compress();
    for (int i = 1; i <= n; ++i)
        fakeupdate(arr[i].x, arr[i].y);
    for (int i = 1; i <= q; ++i)
        fakequery(qr[i].x, qr[i].y, m, inf);
    for (int i = 1; i <= m; ++i)
    {
        pos[i].push_back(0), sort(all(pos[i]));
        pos[i].resize(unique(all(pos[i])) - pos[i].begin());
        bit[i].resize(pos[i].size() + 1);
    }
    for (int i = 1, j = 1; i <= q; ++i)
    {
        while (j <= n && arr[j].z >= qr[i].z)
            update(arr[j].x, arr[j].y, 1), ++j;
        result[qr[i].id] = query(qr[i].x, qr[i].y, m, inf);
    }
    for (int i = 1; i <= q; ++i)
        cout << result[i] << "\n";
}

int main()
{
    ReadData();
    Solve();
    return 0;
}

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