Submission #484382

#	Time	Username	Problem	Language	Result	Execution time	Memory
484382		Mahdi	Examination (JOI19_examination)	C++17	100 / 100	143 ms	6624 KiB

examination

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e5+5;
int n, q, s[N], t[N], a[N], aa[N], b[N], bb[N], c[N], cc[N], ans[N];
vector<pair<pii, pii>>v;
vector<pair<pii, int>>w;

bool cmp(const int &x, const int &y){
    return s[x]+t[x]<s[y]+t[y];
}

bool cpp(const int &x, const int &y){
    return s[x]<s[y];
}

bool ppp(const int &x, const int &y){
    return t[x]<t[y];
}

struct fenwick{
    vector<int>bit=vector<int>(n, 0);
    void add(int i){
        for(int j=i;j<n;j|=(j+1))
            ++bit[j];
    }
    int sum(int i){
        int as=0;
        for(int j=i;j>=0;j=(j&(j+1))-1)
            as+=bit[j];
        return as;
    }
};

int bin1(int x){
    if(s[a[n-1]]<x)
        return n;
    int l=0, r=n-1;
    while(r>l){
        int m=(r+l)/2;
        if(s[a[m]]>=x)
            r=m;
        else
            l=m+1;
    }
    return l;
}

int bin2(int x){
    if(t[b[n-1]]<x)
        return n;
    int l=0, r=n-1;
    while(r>l){
        int m=(r+l)/2;
        if(t[b[m]]>=x)
            r=m;
        else
            l=m+1;
    }
    return l;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=0;i<n;++i)
        cin>>s[i]>>t[i];
    iota(a, a+n, 0);
    iota(b, b+n, 0);
    iota(c, c+n, 0);
    sort(a, a+n, cpp);
    for(int i=0;i<n;++i)
        aa[a[i]]=i;
    sort(b, b+n, ppp);
    for(int i=0;i<n;++i)
        bb[b[i]]=i;
    sort(c, c+n, cmp);
    for(int i=0;i<n;++i)
        cc[c[i]]=i;
    int x, y, z;
    for(int i=0;i<q;++i){
        cin>>x>>y>>z;
        if(z<=x+y)
            w.push_back({{x, y}, i});
        else
            v.push_back({{z, i}, {x, y}});
    }
    sort(all(v));
    sort(all(w));
    reverse(all(v));
    reverse(all(w));
    fenwick A;
    int j=n-1;
    for(auto u:w){
        while(j>=0 && s[a[j]]>=u.F.F)
            A.add(bb[a[j--]]);
        int x=bin2(u.F.S);
        if(x>=0)
            x=A.sum(x-1);
        ans[u.S]=n-j-1-x;
    }
    j=n-1;
    fill(all(A.bit), 0);
    for(auto u:v){
        while(j>=0 && s[c[j]]+t[c[j]]>=u.F.F)
            A.add(aa[c[j--]]);
        int x=bin1(u.S.F);
        if(x>=0)
            x=A.sum(x-1);
        ans[u.F.S]=n-j-1-x;
    }
    j=n-1;
    fill(all(A.bit), 0);
    for(auto u: v){
        while(j>=0 && s[c[j]]+t[c[j]]>=u.F.F)
            A.add(bb[c[j--]]);
        int x=bin2(u.S.S);
        if(x>=0)
            x=A.sum(x-1);
        ans[u.F.S]-=x;
    }
    for(int i=0;i<q;++i)
        cout<<ans[i]<<'\n';
}

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