Submission #1097121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097121		TrinhKhanhDung	Examination (JOI19_examination)	C++14	100 / 100	219 ms	23052 KiB

examination

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18 + 10
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct fen{
    vector<int> tree;
    int n;

    fen(int _n = 0){
        n = _n;
        tree.resize(n + 3, 0);
    }

    void upd(int p, int c){
        for(; p <= n; p += p & -p) tree[p] += c;
    }

    int get(int p){
        int ans = 0;
        for(; p > 0; p -= p & -p) ans += tree[p];
        return ans;
    }

    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

const int MAX = 1e5 + 10;

int N, Q;
int S[MAX], T[MAX], X[MAX], Y[MAX], Z[MAX], ans[MAX];

void process1(vector<pair<ll, ll>> A, vector<array<ll, 3>> queries){
    sort(ALL(A), greater<pair<ll, ll>>());
    sort(ALL(queries), greater<array<ll, 3>>());

    vector<ll> tmp;
    for(auto t: A) tmp.push_back(t.se);
    for(auto t: queries) tmp.push_back(t[1]);
    cps(tmp);

    auto pos = [&](ll c) -> int{
        return lower_bound(ALL(tmp), c) - tmp.begin() + 1;
    };

    fen bit(sz(tmp));
    int i = 0;
    for(auto x: queries){
        while(i < sz(A) && A[i].fi >= x[0]){
            bit.upd(pos(A[i].se), 1);
            i++;
        }
        ans[x[2]] += bit.get(pos(x[1]), sz(tmp));
    }
}

void process2(vector<pair<ll, ll>> A, vector<array<ll, 4>> queries){
    sort(ALL(A), greater<pair<ll, ll>>());
    sort(ALL(queries), greater<array<ll, 4>>());

    vector<ll> tmp;
    for(auto t: A) tmp.push_back(t.se);
    for(auto t: queries) tmp.push_back(t[1]), tmp.push_back(t[2]);
    cps(tmp);

    auto pos = [&](ll c) -> int{
        return lower_bound(ALL(tmp), c) - tmp.begin() + 1;
    };

    fen bit(sz(tmp));
    int i = 0;
    for(auto x: queries){
        while(i < sz(A) && A[i].fi >= x[0]){
            bit.upd(pos(A[i].se), 1);
            i++;
        }
        ans[x[3]] += bit.get(pos(x[1]), pos(x[2]));
    }
}

void solve(){
    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];

    //situation 1: X[i] + Y[i] >= Z[i]
    vector<pair<ll, ll>> A;
    vector<array<ll, 3>> queries1;
    for(int i = 1; i <= N; i++) A.push_back({S[i], T[i]});
    for(int i = 1; i <= Q; i++) if(X[i] + Y[i] >= Z[i]){
        queries1.push_back({X[i], Y[i], i});
    }
    process1(A, queries1);

    //situation 2: X[i] + Y[i] < Z[i]
    //TH1: S[i] <= Z[i] - Y[i]
    A.clear();
    vector<array<ll, 4>> queries2;
    for(int i = 1; i <= N; i++) A.push_back({S[i] + T[i], S[i]});
    for(int i = 1; i <= Q; i++) if(X[i] + Y[i] < Z[i]){
        queries2.push_back({Z[i], X[i], Z[i] - Y[i], i});
    }
    process2(A, queries2);

    //TH2: S[i] > Z[i] - Y[i] > X[i] -> just count T[i] >- Y[i]
    queries1.clear();
    A.clear();
    for(int i = 1; i <= N; i++) A.push_back({S[i], T[i]});
    for(int i = 1; i <= Q; i++) if(X[i] + Y[i] < Z[i]){
        queries1.push_back({Z[i] - Y[i] + 1, Y[i], i});
    }
    process1(A, queries1);

    //print result
    for(int i = 1; i <= Q; i++){
        cout << ans[i] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("task.inp","r",stdin);
//    freopen("task.out","w",stdout);

    int T = 1;
//    cin >> T;
    for(; T; T--) solve();

    return 0;
}

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