Submission #933374

#	Time	Username	Problem	Language	Result	Execution time	Memory
933374		Hanksburger	Examination (JOI19_examination)	C++17	2 / 100	3111 ms	338984 KiB

examination

#include <bits/stdc++.h>
using namespace std;
pair<pair<int, int>, pair<int, int> > b[100005];
pair<int, pair<int, int> > a[100005];
map<pair<int, int>, int> mp;
int ans[100005];
void upd(int x, int y)
{
    for (int i=x; i<=1e9+1; i+=i&(-i))
        for (int j=y; j<=1e9+1; j+=j&(-j))
            mp[{i, j}]++;
}
int qry(int x, int y)
{
    int res=0;
    for (int i=x; i; i-=i&(-i))
        for (int j=y; j; j-=j&(-j))
            res+=mp[{i, j}];
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, ind=1;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[i]={2e9+2-x-y, {1e9+1-x, 1e9+1-y}};
    }
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        b[i]={{2e9+2-z, i}, {1e9+1-x, 1e9+1-y}};
    }
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    for (int i=1; i<=m; i++)
    {
        while (ind<=n && a[ind].first<=b[i].first.first)
        {
            upd(a[ind].second.first, a[ind].second.second);
            ind++;
        }
        ans[b[i].first.second]=qry(b[i].second.first, b[i].second.second);
    }
    for (int i=1; i<=m; i++)
        cout << ans[i] << '\n';
}

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