Submission #1179994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179994		Hamed_Ghaffari	Examination (JOI19_examination)	C++20	100 / 100	294 ms	21916 KiB

examination

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

using pii = pair<int, int>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 1e5+2;

struct Fen {
    int n;
    vector<int> cmp, fen;
    inline void add(int x) { cmp.pb(x); }
    inline void build() {
        sort(all(cmp));
        cmp.resize(unique(all(cmp))-cmp.begin());
        n = SZ(cmp);
        fen.resize(n+1, 0);
    }
    inline void upd(int p, int x) {
        for(p=lower_bound(all(cmp), p)-cmp.begin()+1; p<=n; p+=p&-p) fen[p] += x;
    }
    inline int get(int p) {
        int res=0;
        for(p=upper_bound(all(cmp), p)-cmp.begin(); p; p-=p&-p) res += fen[p];
        return res;
    }
};

struct Fen_2D {
    int n;
    vector<int> cmp;
    vector<Fen> fen;
    inline void add1(int x) { cmp.pb(x); }
    inline void build1() {
        sort(all(cmp));
        cmp.resize(unique(all(cmp))-cmp.begin());
        n = SZ(cmp);
        fen.resize(n+1);
    }
    inline void add2(int x, int y) {
        for(x=lower_bound(all(cmp),x)-cmp.begin()+1; x<=n; x+=x&-x) fen[x].add(y);
    }
    inline void build2() {
        for(int i=1; i<=n; i++) fen[i].build();
    }
    inline void upd(int x, int y, int z) {
        for(x=lower_bound(all(cmp),x)-cmp.begin()+1; x<=n; x+=x&-x) fen[x].upd(y, z);
    }
    inline int get(int x, int y) {
        int res=0;
        for(x=upper_bound(all(cmp),x)-cmp.begin(); x; x-=x&-x) res += fen[x].get(y);
        return res;
    }
} ds;

int n, q, S[MXN], T[MXN], X[MXN], Y[MXN], Z[MXN], U[MXN], G[MXN], ans[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> S[i] >> T[i];
        ds.add1(-S[i]);
    }
    ds.build1();
    for(int i=1; i<=n; i++) ds.add2(-S[i], -T[i]);
    ds.build2();

    for(int i=1; i<=q; i++)
        cin >> X[i] >> Y[i] >> Z[i];
    iota(U+1, U+n+1, 1);
    sort(U+1, U+n+1, [&](int i, int j) { return S[i]+T[i] > S[j]+T[j]; });
    iota(G+1, G+q+1, 1);
    sort(G+1, G+q+1, [&](int i, int j) { return Z[i] > Z[j]; });
    int ptr=1;
    for(int i=1; i<=q; i++) {
        while(ptr<=n && S[U[ptr]]+T[U[ptr]]>=Z[G[i]]) {
            ds.upd(-S[U[ptr]], -T[U[ptr]], 1);
            ptr++;
        }
        ans[G[i]] = ds.get(-X[G[i]], -Y[G[i]]);
    }
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
    return 0;
}

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