Submission #933365

#	Time	Username	Problem	Language	Result	Execution time	Memory
933365		Hanksburger	Examination (JOI19_examination)	C++17	2 / 100	3074 ms	206704 KiB

examination

#include <bits/stdc++.h>
using namespace std;
pair<pair<long long, long long>, pair<long long, long long> > b[100005];
pair<long long, pair<long long, long long> > a[100005];
map<pair<long long, long long>, long long> mp;
long long ans[100005];
void upd(long long x, long long y)
{
    for (long long i=x; i<=(1<<30); i+=i&(-i))
        for (long long j=y; j<=(1<<30); j+=j&(-j))
            mp[{i, j}]++;
}
long long qry(long long x, long long y)
{
    long long res=0;
    for (long long i=x; i; i-=i&(-i))
        for (long long 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);
    long long n, m, ind;
    cin >> n >> m;
    for (long long i=1; i<=n; i++)
    {
        long long x, y;
        cin >> x >> y;
        a[i]={x+y+2, {x+1, y+1}};
    }
    for (long long i=1; i<=m; i++)
    {
        long long x, y, z;
        cin >> x >> y >> z;
        b[i]={{z+2, i}, {x+1, y+1}};
    }
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    ind=n;
    for (long long i=m; i>=1; i--)
    {
        while (ind && a[ind].first>=b[i].first.first)
        {
            upd(a[ind].second.first, a[ind].second.second);
            ind--;
        }
        ans[b[i].first.second]=qry(1<<30, 1<<30)-qry(1<<30, b[i].second.second-1)-qry(b[i].second.first-1, 1<<30)+qry(b[i].second.first-1, b[i].second.second-1);
    }
    for (long long 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