Submission #1309153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309153		999captain	Examination (JOI19_examination)	C++20	0 / 100	154 ms	17712 KiB

examination

#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);
        for(int i = 0;i < posy/B;i++){
            sumy[i]++;
        }
        int k = posy/B;
        for(int i = (k-1)*B + 1;i <= posy;i++){
            valy[i]++;
        }
        int posz = bb(s[pos] + t[pos], ordz);
        for(int i = 0;i < posz/B;i++){
            sumz[i]++;
        }
        k = posz/B;
        for(int i = (k - 1)*B + 1;i <= posz;i++){
            valz[i]++;
        }
    }
     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";
    }
}

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