Submission #512913

#	Time	Username	Problem	Language	Result	Execution time	Memory
512913		couplefire	Examination (JOI19_examination)	C++17	100 / 100	312 ms	14924 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second

const int N = 100005;

struct BIT{
    int bit[N];
    void upd(int x){
        for(; x<N; x = (x|(x+1)))
            ++bit[x];
    }
    int query(int x){
        int res = 0;
        for(; x>=0; x = (x&(x+1))-1)
            res += bit[x];
        return res;
    }
} xt, yt, tt;

int n, q, xm, ym;
pii arr[N];
pair<pii, pii> qs[N];
map<int, int> xmp, ymp;
vector<int> xtmp, ytmp;
int ans[N];

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 0; i<n; ++i)
        cin >> arr[i].f >> arr[i].s, xtmp.push_back(arr[i].f), ytmp.push_back(arr[i].s);
    sort(arr, arr+n, [&](pii a, pii b){return a.f+a.s<b.f+b.s;});
    sort(xtmp.begin(), xtmp.end());
    xtmp.erase(unique(xtmp.begin(), xtmp.end()), xtmp.end());
    xm = xtmp.size();
    for(int i = 0; i<xm; ++i)
        xmp[xtmp[i]] = i;
    sort(ytmp.begin(), ytmp.end());
    ytmp.erase(unique(ytmp.begin(), ytmp.end()), ytmp.end());
    ym = ytmp.size();
    for(int i = 0; i<ym; ++i)
        ymp[ytmp[i]] = i;
    for(int i = 0; i<q; ++i)
        cin >> qs[i].s.f >> qs[i].s.s >> qs[i].f.f, qs[i].f.s = i;
    sort(qs, qs+q);
    for(int i = q-1, j = n-1; i>=0; --i){
        while(j>=0 && arr[j].f+arr[j].s>=qs[i].f.f)
            xt.upd(xmp[arr[j].f]), yt.upd(ymp[arr[j].s]), --j;
        if(qs[i].s.f+qs[i].s.s<=qs[i].f.f){
            int xid = lower_bound(xtmp.begin(), xtmp.end(), qs[i].s.f)-xtmp.begin();
            int yid = lower_bound(ytmp.begin(), ytmp.end(), qs[i].s.s)-ytmp.begin();
            ans[qs[i].f.s] = (n-1-j)-xt.query(xid-1)-yt.query(yid-1);
        }
    }
    sort(qs, qs+q, [&](pair<pii, pii> a, pair<pii, pii> b){return a.s.f<b.s.f;});
    sort(arr, arr+n);
    for(int i = q-1, j = n-1; i>=0; --i){
        while(j>=0 && arr[j].f>=qs[i].s.f)
            tt.upd(ym-1-ymp[arr[j].s]), --j;
        if(qs[i].s.f+qs[i].s.s>qs[i].f.f){
            int yid = lower_bound(ytmp.begin(), ytmp.end(), qs[i].s.s)-ytmp.begin();
            ans[qs[i].f.s] = tt.query(ym-1-yid);
        }
    }
    for(int i = 0; i<q; ++i)
        cout << ans[i] << '\n';
}

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