Submission #578350

#	Time	Username	Problem	Language	Result	Execution time	Memory
578350		OttoTheDino	Examination (JOI19_examination)	C++17	43 / 100	3075 ms	315340 KiB

examination

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

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (ll i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (ll)a.size()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

unordered_map<ll,ll> seg_tree[2] = {};
unordered_map<ll,ll> lazy[2] = {};
 
void upd (ll tp, ll val, ll l, ll r, ll bl, ll br, ll id) {
    seg_tree[tp][id] += val;
    if (l==bl && r==br) {
        lazy[tp][id] += val;
        return;
    }
    ll mid = (bl+br)/2;
    if (r<=mid) upd (tp, val, l, r, bl, mid, 2*id);
    else if (l>mid) upd (tp, val, l, r, mid+1, br, 2*id+1);
    else {
        upd (tp, val, l, mid, bl, mid, 2*id);
        upd (tp, val, mid+1, r, mid+1, br, 2*id+1);
    }
} 
 
ll query (ll tp, ll l, ll r, ll bl, ll br, ll id) {
    if (l==bl && r==br) return seg_tree[tp][id];
    if (bl!=br) {
        lazy[tp][2*id] += lazy[tp][id];
        lazy[tp][2*id+1] += lazy[tp][id];
        seg_tree[tp][2*id] += lazy[tp][id];
        seg_tree[tp][2*id+1] += lazy[tp][id];
        lazy[tp][id] = 0;
    }
    ll mid = (bl+br)/2;
    if (r<=mid) return query (tp, l, r, bl, mid, 2*id);
    if (l>mid) return query (tp, l, r, mid+1, br, 2*id+1);
    return query (tp, l, mid, bl, mid, 2*id) + query (tp, mid+1, r, mid+1, br, 2*id+1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n, q, x = 0; cin >> n >> q;

    vector<pair<ll,ii>> peep;
    vector<pair<ii,ii>> ques;
    ll ans[q+1];

    rep (i,1,n) {
        ll a, b; cin >> a >> b;
        peep.pb({a+b,{a,b}});
    }

    rep (i,1,q) {
        ll a, b, c; cin >> a >> b >> c;
        ques.pb({{max(a+b,c),i},{a,b}});
    }

    sort(all(ques));
    reverse(all(ques));
    sort(all(peep));
    reverse(all(peep));

    rep (i,0,q-1) {
        ll c = ques[i].fi.fi, a = ques[i].se.fi, b = ques[i].se.se, u = ques[i].fi.se;
        while (x < n && peep[x].fi>=c) {
            upd (0, 1, peep[x].se.fi, peep[x].se.fi, 0, 1e9, 1);
            upd (1, 1, peep[x].se.se, peep[x].se.se, 0, 1e9, 1);
            x++;
        }
        ans[u] = query(0,a,1e9,0,1e9,1) + query(1,b,1e9,0,1e9,1) - x;
    }

    rep (i,1,q) cout << ans[i] << "\n";

    return 0;
}

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