Submission #1344336

#TimeUsernameProblemLanguageResultExecution timeMemory
1344336minhtienExamination (JOI19_examination)C++20
2 / 100
3094 ms31332 KiB
#include <bits/stdc++.h>
#define iiii pair<int,pair<int,pair<int,int>>>
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define fi first
#define se second
using namespace std;
const int N=6e5+6;
int n,q;
int a3[N];
vector<int>tree[4*N];
vector<iii>v;
vector<iiii>v1;
map<int,int>v3;
vector<int>z1;
int k1=1;
void f2(){
    sort(z1.begin(),z1.end());
    v3[z1[0]]=k1;
    for(int j=1;j<z1.size();j++){
        if(z1[j]!=z1[j-1]) k1++;
        v3[z1[j]]=k1;
    }
}
vector<int>f(vector<int>&x,vector<int>&y){
    int s=x.size(),s1=y.size();
    vector<int>v2(s+s1);
    merge(x.begin(),x.end(),y.begin(),y.end(),v2.begin());
    return v2;
}
void update(int id,int l,int r,int i,int val){
    if(i>r || i<l){
        return ;
    }
    if(l==r){
        tree[id].push_back(val);
        sort(tree[id].begin(),tree[id].end());
        return ;
    }
    int m=(l+r)/2;
    update(id*2,l,m,i,val);
    update(id*2+1,m+1,r,i,val);
    tree[id]=f(tree[id*2],tree[id*2+1]);
}
vector<int>get(int id,int l,int r,int x,int y){
    if(r<x || l>y) return {};
    if(l>=x && r<=y) return tree[id];
    int m=(l+r)/2;
    vector<int>s1=get(id*2,l,m,x,y);
    vector<int>s2=get(id*2+1,m+1,r,x,y);
    return f(s1,s2);
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >>n >>q;
    for(int i=1;i<=n;i++){
        int x,y;
        cin >>x >>y;
        v.push_back({x,{y,x+y}});
        z1.push_back(x);
        z1.push_back(y);
        z1.push_back(x+y);
    }
    for(int i=1;i<=q;i++){
        int x,y,z;
        cin >>x >>y >>z;
        v1.push_back({x,{y,{z,i}}});
        z1.push_back(x);
        z1.push_back(y);
        z1.push_back(z);
    }
    f2();
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end());
    int j=v.size()-1;
    for(int i=v1.size()-1;i>=0;i--){
        while(j>=0 && v[j].fi>=v1[i].fi){
            update(1,1,k1,v3[v[j].se.fi],v[j].se.se);
            j--;
        }
        vector<int>s3=get(1,1,k1,v3[v1[i].se.fi],k1);
        int t=lower_bound(s3.begin(),s3.end(),v1[i].se.se.fi)-s3.begin();
        int tong=s3.size()-t+1;
        a3[v1[i].se.se.se]=tong;
    }
    for(int i=1;i<=q;i++){
        cout << a3[i]-1 << "\n";
    }
    return 0;
}

/*

10 10
28 2
78 81
39 79
61 31
36 99
90 5
20 55
91 4
48 19
80 7
52 43 78
64 65 171
34 68 124
37 80 161
53 19 123
49 58 109
95 46 30
45 48 60
47 13 54
64 30 144

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...