Submission #1309171

#TimeUsernameProblemLanguageResultExecution timeMemory
1309171999captainExamination (JOI19_examination)C++20
100 / 100
200 ms19388 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int B = 320;
int n,q;
int sumy[321],sumz[321];
int valy[100010],valz[100010];
int s[100010],t[100010];
int x[100010],y[100010],z[100010];
int mapay[100010],mapaz[100010];
int troca[100010];
int ans[100010];
bool ok[100010];
vector<pii> ordy,ordz;

int bb(int x, vector<pii> &v){
    int ini = 0, fim = v.size() - 1;
    while(ini < fim){
        int meio = (ini + fim + 1)/2;
        if(v[meio].first <= x){
            ini = meio;
        }
        else{
            fim = meio - 1;
        }
    }
    if(x < v[0].first){
        return 0;
    }
    return ini + 1;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> t[i];
    }
    for(int i = 1;i <= q;i++){
        cin >> x[i] >> y[i] >> z[i];
        ordy.push_back({y[i] , i});
        ordz.push_back({z[i] , i});
    }
    sort(ordy.begin(), ordy.end());
    sort(ordz.begin(), ordz.end());
    for(int i = 0;i < q;i++){
        mapay[ordy[i].second] = i + 1;
        mapaz[ordz[i].second] = i + 1;
    }
    priority_queue<pii> pq,pqx,pqyz;
    for(int i = 1;i <= n;i++){
        pq.push({s[i] , i});
    }
    for(int i = 1;i <= q;i++){
        pqx.push({x[i] , i});
        pqyz.push({z[i] - y[i] , i});
    }

    while(!pq.empty()){
        int h = pq.top().first, pos = pq.top().second;
        pq.pop();
        while(!pqyz.empty()){
            if(pqyz.top().first > h){
                int a = pqyz.top().second;
                ok[a] = true;
                troca[a] = (sumy[mapay[a]/B] + valy[mapay[a]]) - (sumz[mapaz[a]/B] + valz[mapaz[a]]);
                pqyz.pop();
            }
            else{
                break;
            }
        }
        while(!pqx.empty()){
            if(pqx.top().first > h){
                int a = pqx.top().second;
                if(!ok[a]){ 
                    ans[a] = sumy[mapay[a]/B] + valy[mapay[a]];
                }   
                else{
                    ans[a] = troca[a] + sumz[mapaz[a]/B] + valz[mapaz[a]];
                }
                pqx.pop();
            }
            else{
                break;
            }
        }

        int posy = bb(t[pos], ordy);
        int l = 0, r = posy;
        while(l + B - 1 <= r){
            sumy[l/B]++;
            l += B;
        }
        while(l <= r){
            valy[l]++;
            l++;
        }
        int posz = bb(s[pos] + t[pos], ordz);
        l = 0, r = posz;
        while(l + B - 1 <= r){
            sumz[l/B]++;
            l += B;
        }
        while(l <= r){
            valz[l]++;
            l++;
        }
    }
     while(!pqx.empty()){
            int a = pqx.top().second;
            if(!ok[a]){
                ans[a] = sumy[mapay[a]/B] + valy[mapay[a]];
            }   
            else{
                ans[a] = troca[a] + sumz[mapaz[a]/B] + valz[mapaz[a]];
            }
            pqx.pop();
        }
    for(int i = 1;i <= q;i++){
        cout << ans[i] << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...