제출 #1094145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094145		Gray	Examination (JOI19_examination)	C++17	100 / 100	1279 ms	161260 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define ord_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
const ll MOD = 1e9+7;
const ll INF = 2e18;

struct msegt{
    struct node{
        ord_set items;
    };
    vector<node> t;
    ll sz, rsz;
    msegt(ll N){
        rsz=N;
        sz=N*4;
        t.resize(sz);
    }
    void merge(node &par, node &l, node &r){
        for (auto ch:l.items) par.items.insert(ch);
        for (auto ch:r.items) par.items.insert(ch); 
    }
    void query(ll tl, ll tr, ll v, ll l, ll r, ll x, ll &sum){
        if (tl==l and tr==r){
            // cout << tl << "-" << tr << " * " << x << ": " << t[v].items.size()-t[v].items.order_of_key(x) << ln;
            sum+=t[v].items.size()-t[v].items.order_of_key(x);
        }else if (l>r) return;
        else{
            ll tm = (tl+tr)/2;
            query(tl, tm, v*2, l, min(r, tm), x, sum);
            query(tm+1, tr, v*2+1, max(l, tm+1), tr, x, sum);
        }
    }
    void insert_item(ll tl, ll tr, ll v, ll i, ll x){
        t[v].items.insert(x);
        if (tl==tr){
            return;
        }else{
            ll tm = (tl+tr)/2;
            if (i<=tm){
                insert_item(tl, tm, v*2, i, x);
            }else{
                insert_item(tm+1, tr, v*2+1, i, x);
            }
        }
    }
    ll query(ll l, ll r, ll x){
        ll sum=0;
        query(0, rsz-1, 1, l, r, x, sum);
        return sum;
    }
    void add(ll i, ll x){
        insert_item(0, rsz-1, 1, i, x);
    }
};

void solve(){
    ll n, q; cin >> n >> q;
    vector<pair<ll, ll>> scores(n);
    vector<ll> sums(n);
    for (ll i=0; i<n; i++){
        cin >> scores[i].ff >> scores[i].ss;
        sums[i] = i;
    }
    vector<pair<pair<ll, ll>, pair<ll, ll>>> qs(q);
    for (ll i=0; i<q; i++){
        cin >> qs[i].ff.ff >> qs[i].ff.ss >> qs[i].ss.ff;
        qs[i].ss.ss=i;
    }
    sort(scores.begin(), scores.end());
    // for (auto ch:scores){
    //     cout << ch.ff << "-" << ch.ss << ' ';
    // }
    // cout << ln;
    sort(sums.rbegin(), sums.rend(), [&](ll op1, ll op2){
        return scores[op1].ff+scores[op1].ss<scores[op2].ff+scores[op2].ss;
    });
    // return;
    vector<ll> ys(n);
    for (ll i=0; i<n; i++) ys[i]=scores[i].ss;
    // return;
    msegt tr(n);
    sort(qs.rbegin(), qs.rend(), [](auto op1, auto op2){
        return op1.ss.ff<op2.ss.ff;
    });
    vector<ll> res(q);
    ll l=0;
    // return;
    for (ll i=0; i<q; i++){
        while (l<n and qs[i].ss.ff<=scores[sums[l]].ff+scores[sums[l]].ss){
            tr.add(sums[l], scores[sums[l]].ss);
            l++;
        }
        // cout << qs[i].ss.ss << ": " << l << " -> ";
        pair<ll, ll> seek = {qs[i].ff.ff, 0};
        ll ind = lower_bound(scores.begin(), scores.end(), seek)-scores.begin();
        // cout << ind << ln;
        res[qs[i].ss.ss] = tr.query(ind, n-1, qs[i].ff.ss);
    }
    for (ll i=0; i<q; i++) cout << res[i] << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) solve();
}

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