Submission #1282074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282074		peanut	Examination (JOI19_examination)	C++20	43 / 100	393 ms	29968 KiB

examination

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct query {int x, y, z, id;};
struct info {int comp_x, orig_x, orig_y;};
int n, q;
info a[maxn];
query queries[maxn];
int nx;
vector<int> pos[maxn];
vector<int> BIT[maxn];

void fakeupd(int x, int y)
{
    for (; x <= nx; x += x & (-x)) pos[x].pb(y);
}
void fakeget(int x, int y)
{
    for (; x; x -= x & (-x)) pos[x].pb(y);
}

void compress()
{
    for (int i = 1; i <= nx; ++i)
    {
        if (pos[i].empty()) continue;
        pos[i].pb(INT_MIN);
        sort(all(pos[i]));
        pos[i].erase(unique(all(pos[i])), pos[i].end());
        BIT[i].assign(sz(pos[i]) + 5, 0);
    }
}
int getidx(int x, int y)
{
    return lower_bound(all(pos[x]), y) - pos[x].begin() + 1;
}
void realupd(int x, int y, int val)
{
    for (int i = x; i <= nx; i += i & (-i))
        for (int j = getidx(i, y); j <= sz(pos[i]); j += j & (-j)) BIT[i][j] += val;
}
int realget(int x, int y)
{
    int res = 0;
    for (int i = x; i > 0; i -= i & (-i))
        for (int j = getidx(i, y); j > 0; j -= j & (-j)) res += BIT[i][j];
    return res;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> q;
    vector<int> comp;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].orig_x >> a[i].orig_y;
        comp.pb(a[i].orig_x);
    }

    for (int i = 1; i <= q; ++i)
    {
        cin >> queries[i].x >> queries[i].y >> queries[i].z;
        comp.pb(queries[i].x);
        queries[i].id = i-1;
    }

    sort(a+1, a+1+n, [](info &a, info &b) {return a.orig_x + a.orig_y > b.orig_x + b.orig_y;});
    sort(queries+1, queries+1+q, [](query &a, query &b) {return a.z > b.z;});

    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    nx = sz(comp);
    for (int i = 1; i <= n; ++i)
    {
        a[i].comp_x = lower_bound(all(comp), a[i].orig_x) - comp.begin() + 1;
        fakeupd(nx - a[i].comp_x + 1, -a[i].orig_y);
    }
    for (int i = 1; i <= q; ++i)
    {
        queries[i].x = lower_bound(all(comp), queries[i].x) - comp.begin() + 1;
        fakeget(nx - queries[i].x + 1, -queries[i].y);
    }
    compress();

    vector<int> ans(q);
    int idx = 1;
    for (int i = 1; i <= q; ++i)
    {
        while (idx <= n && a[idx].orig_x + a[idx].orig_y >= queries[i].z)
        {
            realupd(nx - a[idx].comp_x + 1, -a[idx].orig_y, 1);
            ++idx;
        }
        ans[queries[i].id] = realget(nx - queries[i].x + 1, -queries[i].y);
    }

    for (auto i : ans) cout << i << '\n';
    return 0;
}

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