Submission #888119

#	Time	Username	Problem	Language	Result	Execution time	Memory
888119		boyliguanhan	Examination (JOI19_examination)	C++17	100 / 100	504 ms	26448 KiB

examination

#include<bits/stdc++.h>
using namespace std;
struct st {
    int x, y, z, i;
};
vector<st> v;
struct fenwick {
    int t[400010];
    void upd(int n, int x) {
        for(;n<=4e5;n+=n&-n)
            t[n]+=x;
    }
    int q(int n) {
        int x = 0;
        for(;n;n-=n&-n)
            x+=t[n];
        return x;
    }
    int Q(int x) {
        return q(4e5)-q(x-1);
    }
} A,B;
int ans[100100];
map<int,int> mp;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mp[a], mp[b];
        v.push_back({a,b,a+b,0});
    }
    for(int i = 1; i <= q; i++) {
        int x,y,z;
        cin >> x >> y>> z;
        mp[x],mp[y];
        v.push_back({x,y,max(z,x+y),i});
    }
    sort(v.begin(),v.end(),[](st a, st b) {
        return (a.z-b.z?a.z>b.z:a.i<b.i);
    });
    int cnt = 0;
    for(auto &i: mp)
        i.second=++cnt;
    cnt=0;
    for(auto i: v)
        if(i.i)
            ans[i.i]=A.Q(mp[i.x])+B.Q(mp[i.y])-cnt;
        else
            A.upd(mp[i.x],1),B.upd(mp[i.y],1),cnt++;
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

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