Submission #933374

#TimeUsernameProblemLanguageResultExecution timeMemory
933374HanksburgerExamination (JOI19_examination)C++17
2 / 100
3111 ms338984 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...