Submission #896452

#	Time	Username	Problem	Language	Result	Execution time	Memory
896452		Andrey	Examination (JOI19_examination)	C++14	100 / 100	974 ms	314388 KiB

examination

#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> seg(3000001,{-1,-1});
vector<long long> wow[3000001];
vector<long long> wut[3000001];
long long p = 0;

long long banana(const vector<long long>& haha, long long a) {
    if(haha.empty() || haha[haha.size()-1] < a) {
        return 0;
    }
    long long l = 0,r = haha.size()-1;
    while(l < r) {
        long long m = (l+r)/2;
        if(haha[m] >= a) {
            r = m;
        }
        else {
            l = m+1;
        }
    }
    return haha.size()-l;
}

void ins(long long l, long long r, long long x, long long pos, long long y, long long sb) {
    wow[x].push_back(y);
    wut[x].push_back(sb);
    if(l == r) {
        return;
    }
    long long m = (l+r)/2;
    if(pos <= m) {
        if(seg[x].first == -1) {
            p++;
            seg[x] = {p,seg[x].second};
        }
        ins(l,m,seg[x].first,pos,y,sb);
    }
    else {
        if(seg[x].second == -1) {
            p++;
            seg[x] = {seg[x].first,p};
        }
        ins(m+1,r,seg[x].second,pos,y,sb);
    }
}

long long calc(long long l, long long r, long long x, long long ql, long long qr, bool yeah, long long a) {
    if(x == -1) {
        return 0;
    }
    if(ql == l && qr == r) {
        if(yeah) {
            return banana(wow[x],a);
        }
        else {
            return banana(wut[x],a);
        }
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        return calc(l,m,seg[x].first,ql,qr,yeah,a);
    }
    else if(ql > m) {
        return calc(m+1,r,seg[x].second,ql,qr,yeah,a);
    }
    else {
        return calc(l,m,seg[x].first,ql,m,yeah,a)+calc(m+1,r,seg[x].second,m+1,qr,yeah,a);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,a,b,c;
    cin >> n >> q;
    for(long long i = 0; i < n; i++) {
        cin >> a >> b;
        ins(0,INT_MAX,0,a,b,a+b);
    }
    for(int i = 0; i <= 3000000; i++) {
        sort(wut[i].begin(),wut[i].end());
        sort(wow[i].begin(),wow[i].end());
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b >> c;
        if(a+b >= c) {
            cout << calc(0,INT_MAX,0,a,INT_MAX,true,b) << "\n";
        }
        else {
            cout << calc(0,INT_MAX,0,a,c-b,false,c)+calc(0,INT_MAX,0,c-b+1,INT_MAX,true,b) << "\n";
        }
    }
    return 0;
}

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