제출 #1272438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272438		huudai	Examination (JOI19_examination)	C++20	100 / 100	135 ms	6204 KiB

examination

#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define MASK(i) (1ll<<(i))
#define BI(mask,i) (((mask)>>(i))&1)
#define x0 ___x0
#define y0 ___y0
#define pos POSDFSD
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a = 1ll*a*b%mod;
//}

template <class X, class Y>
    bool maximize (X&x, const Y&y){
        if (x>=y) return false;
        x = y;
        return true;
    }

template <class X, class Y>
    bool minimize (X&x, const Y&y){
        if (x<=y) return false;
        x = y;
        return true;
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////
//const int lim = , limit =, mod = ;
const int lim = 1e5, limit = lim+5, lim2 = 2e5, limit2 = lim2+5;

struct ele{
    int t1, t2, sum, id;
};

ele query[limit], A[limit];
int n, q;

namespace sub1{
    void process(){
        for (int tv = 1; tv<=q; tv++){
            int T1 = query[tv].t1, T2 = query[tv].t2, SUM = query[tv].sum;
            int ret = 0;
            for (int i=1; i<=n; i++){
                if (A[i].t1>=T1 && A[i].t2>=T2 && A[i].sum>=SUM) ret++;
            }
            cout<<ret<<"\n";
        }
    }
}

bool compsum(const ele&a, const ele&b){
    return a.sum >b.sum;
}

namespace sub4{
    int BIT[limit2];
    vector <int> ds;
    int ans[limit];
    void update (int id, int val){
        while (id<=lim2){
            BIT[id] += val;
            id+=(id&(-id));
        }
    }
    //
    int get (int id){
        int ret = 0;
        while (id>0){
            ret += BIT[id];
            id&=id-1;
        }
        return ret;
    }
    //
    int finds (int val){
        int l = 1, r = ds.size()-1, ret = 1;
        while (l<=r){
            int mid = (l+r)/2;
            if (ds[mid]>=val){
                ret = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        return ret;
    }
    //
    void compress1 (){
        ds.pb(-1);
        for (int i=1; i<=n; i++){
            ds.pb(A[i].t1);
        }
        for (int i=1; i<=q; i++){
            ds.pb(query[i].t1);
        }
        sort (ds.begin(), ds.end());
        ds.erase (unique(ds.begin(), ds.end()), ds.end());
        for (int i=1; i<=n; i++){
            A[i].t1 = finds (A[i].t1);
        }
        for (int i=1; i<=q; i++){
            query[i].t1 = finds (query[i].t1);
        }
    }
    //
    void compress2 (){
        ds.clear();
        while (!ds.empty()) ds.pop_back();
        ds.pb(-1);
        for (int i=1; i<=n; i++){
            ds.pb(A[i].t2);
        }
        for (int i=1; i<=q; i++){
            ds.pb(query[i].t2);
        }
        sort (ds.begin(), ds.end());
        ds.erase (unique(ds.begin(), ds.end()), ds.end());
        for (int i=1; i<=n; i++){
            A[i].t2 = finds (A[i].t2);
        }
        for (int i=1; i<=q; i++){
            query[i].t2 = finds (query[i].t2);
        }
    }
    //
    void process(){
        compress1 ();
        compress2 ();
        sort (A+1, A+n+1, compsum);
        sort (query+1, query+q+1, compsum);
        int cur = 1;
        for (int i=1; i<=q; i++){
            int sumq = query[i].sum, id = query[i].id;
            while (cur<=n && A[cur].sum>=sumq){
                cur++;
            }
            ans[id] = cur-1;
        }
        //
        cur = 1;
        for (int i=1; i<=q; i++){
            int sumq = query[i].sum, id = query[i].id;
            while (cur<=n && A[cur].sum>=sumq){
                update (A[cur].t1, 1);
                cur++;
            }
            ans[id] -= get (query[i].t1-1);
        }
        //
        cur = 1;
        for (int i=1; i<=lim2; i++) BIT[i] = 0;
        for (int i=1; i<=q; i++){
            int sumq = query[i].sum, id = query[i].id;
            while (cur<=n && A[cur].sum>=sumq){
                update (A[cur].t2, 1);
                cur++;
            }
            ans[id] -= get (query[i].t2-1);
        }
        for (int i=1; i<=q; i++) cout<<ans[i]<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
    // freopen("ANHDEP.INP", "r", stdin);
    // freopen("ANHDEP.OUT", "w", stdout);
    cin>>n>>q;
    for (int i=1; i<=n; i++){
        cin>>A[i].t1>>A[i].t2;
        A[i].sum = A[i].t1 + A[i].t2;
        A[i].id = 0;
    }
    for (int i=1; i<=q; i++){
        cin>>query[i].t1>>query[i].t2>>query[i].sum;
        maximize (query[i].sum, query[i].t1+query[i].t2);
        query[i].id = i;
    }
    if (n*q<=10000000) sub1::process();
    else sub4::process();
}

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