제출 #306699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306699		jainbot27	Examination (JOI19_examination)	C++17	100 / 100	2724 ms	158712 KiB

examination

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

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 1e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
using node = ordered_set;
int n, ptr = 0, q, gl, ctr, ans[mxN]; ar<int, 3> v[mxN], w[mxN]; ar<int, 4> quer[mxN];
ordered_set st[mxN*4];
int qry(int l, int r, int lx = 0, int rx = n-1, int node = 0){
    if(l <= lx && r >= rx){
        // cout << gl << "{";
        // trav(x, st[node]) cout << x.f << " ";
        // cout << "}\n";
        return siz(st[node]) - st[node].order_of_key({gl,-1});
    }
    if(lx > r || rx < l){
        return 0;
    }
    int m = (lx + rx)/2;
    return qry(l, r, lx, m, node*2+1) + qry(l, r, m+1, rx, node*2+2);
}
void update(int pos, int nxt, int lx = 0, int rx = n-1, int x = 0){
    st[x].insert({nxt, ctr});
    if(lx == rx) return;
    int m = (lx + rx)/2;
    if(pos <= m){
        update(pos, nxt, lx, m, x*2+1);
    }
    else{
        update(pos, nxt, m+1, rx, x*2+2);
    }

}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    F0R(i, n){
        cin >> v[i][0] >> v[i][1];
        v[i][2] = v[i][0] + v[i][1];
        w[i] = v[i];
    }
    sort(v, v+n);
    sort(w, w+n, [](ar<int, 3> e1, ar<int, 3> e2){
        return e1[1] > e2[1];
    });
    F0R(i, q){
        cin >> quer[i][0] >> quer[i][1] >> quer[i][2];
        quer[i][3] = i;
    }
    sort(quer, quer+q, [](ar<int, 4> e1, ar<int, 4> e2){
        return e1[1] > e2[1];
    });
    F0R(i, q){
        while(ptr < n && w[ptr][1] >= quer[i][1]){
            int x = lower_bound(v, v+n,(ar<int,3>) {w[ptr][0], -1, -1}) - v;
            // cout << w[ptr][2] << nl;
            update(x, w[ptr][2]);
            ctr++; ptr++;
        } 
        gl = quer[i][2];
        ans[quer[i][3]] = qry(lower_bound(v, v+n, (ar<int, 3>){quer[i][0], -1, -1}) - v, n-1);
        // cout << ptr << " " << quer[i][2] << " " << quer[i][3] << " " << ans[quer[i][3]] << " " <<  lower_bound(v, v+n, (ar<int, 3>){quer[i][0], -1, -1}) - v << nl;
    }
    F0R(i, q){
        cout << ans[i] << nl;
    }
    return 0;
}

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