Submission #964440

#	Time	Username	Problem	Language	Result	Execution time	Memory
964440		Unforgettablepl	Examination (JOI19_examination)	C++17	41 / 100	80 ms	15424 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct fenwick{
    int n;vector<int> tree;
    fenwick(int n):n(n+1),tree(n+2){}
    int get(int x){
        int ans = 0;
        x++;
        while(x){
            ans+=tree[x];
            x-=x&-x;
        }
        return ans;
    }
    void add(int x){
        x++;
        while(x<=n){
            tree[x]++;
            x+=x&-x;
        }
    }
};

int ans[100001];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> students1;
    vector<tuple<int,int,int>> students2;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        students1.emplace_back(x,y);
        students2.emplace_back(x+y,x,y);
    }
    vector<tuple<int,int,int>> queries1;
    vector<tuple<int,int,int,int>> queries2;
    for(int i=1;i<=q;i++){
        int a,b,c;cin>>a>>b>>c;
        if(a+b>=c)queries1.emplace_back(a,b,i);
        else queries2.emplace_back(c,a,b,i);
    }
    sort(queries1.rbegin(),queries1.rend());
    sort(queries2.rbegin(),queries2.rend());
    sort(students1.rbegin(),students1.rend());
    sort(students2.rbegin(),students2.rend());
    auto iter = students1.begin();
    fenwick f1(100000);
    fenwick f2(100000);
    for(auto[a,b,idx]:queries1){
        while(iter!=students1.end() and iter->first>=a){
            f1.add(iter->second);
            iter++;
        }
        ans[idx] = f1.get(100000)-f1.get(b-1);
    }
    for(int&i:f1.tree)i=0;
    auto iter2 = students2.begin();
    for(auto[c,a,b,idx]:queries2){
        while(iter2!=students2.end() and get<0>(*iter2)>=c){
            f1.add(get<1>(*iter2));
            f2.add(get<2>(*iter2));
            iter2++;
        }
        ans[idx] = f1.get(100000)-f1.get(a-1)-f2.get(b-1);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

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