Submission #964442

#	Time	Username	Problem	Language	Result	Execution time	Memory
964442		Unforgettablepl	Examination (JOI19_examination)	C++17	0 / 100	99 ms	11320 KiB

examination

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

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

#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();
    orderedset f1;
    orderedset f2;
    int curradded = 0;
    for(auto[a,b,idx]:queries1){
        while(iter!=students1.end() and iter->first>=a){
            f1.insert(iter->second);
            iter++;
            curradded++;
        }
        ans[idx] = curradded-f1.order_of_key(b-1);
    }
    f1.clear();
    auto iter2 = students2.begin();
    curradded=0;
    for(auto[c,a,b,idx]:queries2){
        while(iter2!=students2.end() and get<0>(*iter2)>=c){
            f1.insert(get<1>(*iter2));
            f2.insert(get<2>(*iter2));
            iter2++;
            curradded++;
        }
        ans[idx] = curradded-f1.order_of_key(a-1)-f2.order_of_key(b-1);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

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