Submission #839444

#	Time	Username	Problem	Language	Result	Execution time	Memory
839444		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	902 ms	50332 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define fi first
#define se second
int n,q;
pair <int,int> a[100100];
struct qrr{
    int x,y,z,id;
    bool operator < (const qrr &p)const{
        return z > p.z;
    }
} qr[100100];
vector <int> nen_x,nen_y;
vector <int> BIT[200100];
vector <int> VAL[200100];
int ans[100100];
int f(vector <int> &b, int x){
    return lower_bound(b.begin(),b.end(),x) - b.begin();
}
void AddQuery(int x,int y){
    x = f(nen_x,x);
    for (;x > 0;x -= (x & (-x))){
        VAL[x].push_back(y);
    }
}
void AddUpdate(int x,int y){
    x = f(nen_x,x);
    for (;x < nen_x.size();x += (x & (-x))){
        VAL[x].push_back(y);
    }
}
void update(int x,int y){
    x = f(nen_x,x);
    for (;x < nen_x.size();x += x & -x){
        for (int j = f(VAL[x],y);j < VAL[x].size(); j += j & -j){
            BIT[x][j] ++;
        }
    }

}
int query(int x,int y){
    x = f(nen_x,x);
    int res = 0;
    for (;x > 0;x -= x & -x){
        for (int j = f(VAL[x],y);j > 0;j -= j & -j){
            res += BIT[x][j];
        }
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>q;
    for (int i = 1;i <= n;i ++){
        cin>>a[i].fi>>a[i].se;
        nen_x.push_back(a[i].fi);
    }
    for (int i = 1;i <= q;i ++){
        cin>>qr[i].x>>qr[i].y>>qr[i].z;
        nen_x.push_back(qr[i].x-1);
        qr[i].id = i;
    }
    sort(qr+1,qr+1+q);
    nen_x.push_back(-1);
    nen_x.push_back(INF);
    sort(nen_x.begin(),nen_x.end());
    nen_x.resize(unique(nen_x.begin(),nen_x.end()) - nen_x.begin());
    for (int i = 1;i <= n;i ++){
        AddUpdate(a[i].fi,a[i].se);
    }
    for (int i = 1;i <= q;i ++){
        AddQuery(qr[i].x-1,INF);
        AddQuery(INF,qr[i].y-1);
        AddQuery(qr[i].x-1,qr[i].y-1);
    }
    for (int i = 1;i < nen_x.size();i++){
        VAL[i].push_back(-1);
        sort(VAL[i].begin(),VAL[i].end());
        VAL[i].resize(unique(VAL[i].begin(),VAL[i].end()) - VAL[i].begin());
        BIT[i].resize(VAL[i].size());
    }
    /*for (auto x:nen_x){
        cout<<x<<' ';
    }
    cout<<'\n';
    cout<<'\n';
    for (int i = 1;i < nen_x.size();i++){
        for (auto x:VAL[i]){
            cout<<x<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
    for (int i = 1;i < nen_x.size();i++){
        for (auto x:BIT[i]){
            cout<<x<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';*/
    sort(a+1,a+1+n,[=](pair <int,int> a,pair <int,int> b){return a.first + a.second > b.first + b.second;});
    int cur = 1;
    for (int i = 1;i <= q;i ++){
        while (cur <= n && a[cur].fi + a[cur].se >= qr[i].z){
            //cout<<a[cur].fi<<' '<<a[cur].se<<' '<<qr[i].z<<'\n';
            update(a[cur].fi,a[cur].se);
            cur++;
        }
        ans[qr[i].id] = (cur - 1) - query(qr[i].x-1,INF) - query(INF,qr[i].y-1) + query(qr[i].x-1,qr[i].y-1);
    }
    for (int i = 1;i <= q;i++){
        cout<<ans[i]<<'\n';
    }
    cout<<'\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void AddUpdate(int, int)':
examination.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (;x < nen_x.size();x += (x & (-x))){
      |           ~~^~~~~~~~~~~~~~
examination.cpp: In function 'void update(int, int)':
examination.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (;x < nen_x.size();x += x & -x){
      |           ~~^~~~~~~~~~~~~~
examination.cpp:36:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = f(VAL[x],y);j < VAL[x].size(); j += j & -j){
      |                                  ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 1;i < nen_x.size();i++){
      |                    ~~^~~~~~~~~~~~~~

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