Submission #484154

#	Time	Username	Problem	Language	Result	Execution time	Memory
484154		Mahfel	Examination (JOI19_examination)	C++17	100 / 100	255 ms	28936 KiB

examination

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<pair<ll,ll>,ll>> vp;
#define int ll
const int MXN = 5e5 + 20 , Inf = 1e9 + 7;
vector<pair<pair<int,int> , int>> q1, q2, a;
int ans[MXN] , x[MXN] , y[MXN] , z[MXN] , A[MXN] , B[MXN];
int n,q;

struct fenwick {
    int size;
    vector<int> bit;
    fenwick(int n) {
        size = n;
        bit.assign(n , 0);
    }
    void add(int i , int k) {
        for(; i < size ; i |= (i+1)) {
            bit[i] += k;
        }
    }
    int sum(int i) {
        int res = 0;
        for(; i >= 0 ; i = (i&(i+1))-1) {
            res += bit[i];
        }
        return res;
    }
    int sum(int l , int r) {
        return (l == 0 ? sum(r) : sum(r)-sum(l-1));
    }
};

void compress(vp &a , vp &b) {
    vector<int> tmp;
    for(auto p : a) {
        tmp.push_back(p.first.first); tmp.push_back(p.first.second);
    }
    for(auto p : b) {
        tmp.push_back(p.first.first); tmp.push_back(p.first.second);
    }
    sort(tmp.begin() , tmp.end());
    int us = unique(tmp.begin() , tmp.end()) - tmp.begin();
    for(auto &p : a) {
        p.first.first = lower_bound(tmp.begin() , tmp.end() , p.first.first) - tmp.begin()+1;
        p.first.second = lower_bound(tmp.begin() , tmp.end() , p.first.second) - tmp.begin()+1;
    }
    for(auto &p : b) {
        p.first.first = lower_bound(tmp.begin() , tmp.end() , p.first.first) - tmp.begin()+1;
        p.first.second = lower_bound(tmp.begin() , tmp.end() , p.first.second) - tmp.begin()+1;
    }
}

void solve1(vp a , vp q) {
    compress(a , q);
    fenwick cnt(MXN);
    sort(a.rbegin() , a.rend()); sort(q.rbegin() , q.rend());
    a.push_back({{-Inf , -Inf} , -1});
    int ptr = 0;
    for(auto query : q) {
        while(a[ptr].first.first >= query.first.first) {
            cnt.add(a[ptr++].first.second , 1);
        }
        ans[query.second] = cnt.sum(query.first.second , cnt.size-1);
    }
}
void solve2(vp a , vp q) {
    compress(a , q);
    fenwick cntx(MXN) , cnty(MXN);
    sort(a.begin() , a.end() , [&](pair<pair<int,int>,int> x , pair<pair<int,int>,int> y) {
        return A[x.second]+B[x.second] > A[y.second]+B[y.second];
    });
    sort(q.begin() , q.end() , [&](pair<pair<int,int>,int> x , pair<pair<int,int>,int> y) {
        return z[x.second] > z[y.second];
    });
    a.push_back({{-Inf , -Inf} , MXN-1});
    int ptr = 0;
    for(auto query : q) {
        while(A[a[ptr].second]+B[a[ptr].second] >= z[query.second]) {
            cntx.add(a[ptr].first.first , 1);
            cnty.add(a[ptr].first.second , 1);
            ptr++;
        }
        ans[query.second] = ptr-cntx.sum(0 , query.first.first-1)-cnty.sum(0 , query.first.second-1);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> q;
    a.resize(n);
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i].first.first >> a[i].first.second;
        a[i].second = i;
        A[i] = a[i].first.first; B[i] = a[i].first.second;
    }
    for(int i = 0 ; i < q ; i++) {
        cin >> x[i] >> y[i] >> z[i];
        if(x[i]+y[i] >= z[i]) q1.push_back({{x[i] , y[i]} , i});
        else q2.push_back({{x[i] , y[i]} , i});
    }
    solve2(a , q2); solve1(a , q1); 

    for(int i = 0 ; i < q ; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'void compress(vp&, vp&)':
examination.cpp:44:9: warning: unused variable 'us' [-Wunused-variable]
   44 |     int us = unique(tmp.begin() , tmp.end()) - tmp.begin();
      |         ^~

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