oj.uz

Submission #578349

# Submission time Handle Problem Language Result Execution time Memory
578349 2022-06-16T12:09:18 Z OttoTheDino Examination (JOI19_examination) C++17
2 / 100
 3000 ms 47960 KB 
#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;

map<ll,ll> seg_tree[2] = {};
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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 264 ms 33344 KB Output is correct
8 Correct 274 ms 33480 KB Output is correct
9 Correct 277 ms 33348 KB Output is correct
10 Correct 146 ms 16936 KB Output is correct
11 Correct 142 ms 16844 KB Output is correct
12 Correct 22 ms 596 KB Output is correct
13 Correct 289 ms 33368 KB Output is correct
14 Correct 279 ms 33380 KB Output is correct
15 Correct 270 ms 33400 KB Output is correct
16 Correct 125 ms 16976 KB Output is correct
17 Correct 141 ms 16828 KB Output is correct
18 Correct 19 ms 688 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 47960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 47960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 264 ms 33344 KB Output is correct
8 Correct 274 ms 33480 KB Output is correct
9 Correct 277 ms 33348 KB Output is correct
10 Correct 146 ms 16936 KB Output is correct
11 Correct 142 ms 16844 KB Output is correct
12 Correct 22 ms 596 KB Output is correct
13 Correct 289 ms 33368 KB Output is correct
14 Correct 279 ms 33380 KB Output is correct
15 Correct 270 ms 33400 KB Output is correct
16 Correct 125 ms 16976 KB Output is correct
17 Correct 141 ms 16828 KB Output is correct
18 Correct 19 ms 688 KB Output is correct
19 Execution timed out 3078 ms 47960 KB Time limit exceeded
20 Halted 0 ms 0 KB -