oj.uz

Submission #715260

# Submission time Handle Problem Language Result Execution time Memory
715260 2023-03-26T09:56:01 Z Nelt Examination (JOI19_examination) C++17
43 / 100
 526 ms 204612 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5 + 5;
vv(ll) st[N * 12];
ll L[N * 12], R[N * 12], ptr = 2;
ll modify(ll pos, ll val, ll l = 0, ll r = 1e9, ll v = 0)
{
    if (v == 0)
        v = ptr++;
    if (l == r)
    {
        st[v].pb(val);
        return v;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid)
        L[v] = modify(pos, val, l, mid, L[v]);
    else
        R[v] = modify(pos, val, mid + 1, r, R[v]);
    return v;
}
ll query(ll i, ll j, ll k, ll l = 0, ll r = 1e9, ll v = 0)
{
    if (r < i or l > j)
        return 0;
    if (!v)
        return 0;
    if (i <= l and r <= j)
        return st[v].size() - (lower_bound(allc(st[v]), k) - st[v].begin());
    ll mid = (l + r) >> 1;
    return query(i, j, k, l, mid, L[v]) + query(i, j, k, mid + 1, r, R[v]);
}
void build(ll l, ll r, ll v)
{
    if (!v)
        return;
    if (l == r)
    {
        sort(allc(st[v]));
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, L[v]);
    build(mid + 1, r, R[v]);
    merge(allc(st[L[v]]), allc(st[R[v]]), back_inserter(st[v]));
}


vv(ll) st1[N * 12];
ll L1[N * 12], R1[N * 12], ptr1 = 2;
ll modify1(ll pos, ll val, ll l = 0, ll r = 1e9, ll v = 0)
{
    if (v == 0)
        v = ptr1++;
    if (l == r)
    {
        st1[v].pb(val);
        return v;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid)
        L1[v] = modify1(pos, val, l, mid, L1[v]);
    else
        R1[v] = modify1(pos, val, mid + 1, r, R1[v]);
    return v;
}
ll query1(ll i, ll j, ll k, ll l = 0, ll r = 1e9, ll v = 0)
{
    if (r < i or l > j)
        return 0;
    if (!v)
        return 0;
    if (i <= l and r <= j)
        return st1[v].size() - (lower_bound(allc(st1[v]), k) - st1[v].begin());
    ll mid = (l + r) >> 1;
    return query1(i, j, k, l, mid, L1[v]) + query1(i, j, k, mid + 1, r, R1[v]);
}
void build1(ll l, ll r, ll v)
{
    if (!v)
        return;
    if (l == r)
    {
        sort(allc(st1[v]));
        return;
    }
    ll mid = (l + r) >> 1;
    build1(l, mid, L1[v]);
    build1(mid + 1, r, R1[v]);
    merge(allc(st1[L1[v]]), allc(st1[R1[v]]), back_inserter(st1[v]));
}
void solve()
{
    ll n, q;
    cin >> n >> q;
    pp(ll, ll) x[n];
    for (auto &i : x)
        cin >> i.F >> i.S;
    sort(all(x));
    for (auto i : x)
    {
        modify(i.F, i.S, 0, 1e9, 1);
        modify1(i.F, i.F + i.S, 0, 1e9, 1);
    }
    build(0, 1e9, 1);
    build1(0, 1e9, 1);
    ll a, b, c, ans;
    while (q--)
    {
        cin >> a >> b >> c;
        ans = 0;
        if (a <= c - b)
            ans += query1(a, c - b, c, 0, 1e9, 1);
        if (c - b + 1 <= 1e9)
            ans += query(max(c - b + 1, a), 1e9, b, 0, 1e9, 1);
        cout << ans << endl;
    }
}
/*

*/
int main()
{
    sync
        // precomp();
        ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case " << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56692 KB Output is correct
2 Correct 31 ms 56660 KB Output is correct
3 Correct 29 ms 56656 KB Output is correct
4 Correct 35 ms 56636 KB Output is correct
5 Correct 32 ms 56652 KB Output is correct
6 Correct 36 ms 56640 KB Output is correct
7 Correct 47 ms 62900 KB Output is correct
8 Correct 48 ms 62864 KB Output is correct
9 Correct 48 ms 62820 KB Output is correct
10 Correct 50 ms 62868 KB Output is correct
11 Correct 42 ms 58580 KB Output is correct
12 Correct 36 ms 58568 KB Output is correct
13 Correct 50 ms 62856 KB Output is correct
14 Correct 48 ms 62924 KB Output is correct
15 Correct 48 ms 62832 KB Output is correct
16 Correct 35 ms 58512 KB Output is correct
17 Correct 50 ms 62884 KB Output is correct
18 Correct 36 ms 58436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 123456 KB Output is correct
2 Correct 370 ms 123636 KB Output is correct
3 Correct 345 ms 123504 KB Output is correct
4 Correct 349 ms 123612 KB Output is correct
5 Correct 173 ms 110000 KB Output is correct
6 Correct 145 ms 109948 KB Output is correct
7 Correct 299 ms 123636 KB Output is correct
8 Correct 308 ms 123636 KB Output is correct
9 Correct 271 ms 123592 KB Output is correct
10 Correct 156 ms 107944 KB Output is correct
11 Correct 276 ms 123384 KB Output is correct
12 Correct 141 ms 107924 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 123456 KB Output is correct
2 Correct 370 ms 123636 KB Output is correct
3 Correct 345 ms 123504 KB Output is correct
4 Correct 349 ms 123612 KB Output is correct
5 Correct 173 ms 110000 KB Output is correct
6 Correct 145 ms 109948 KB Output is correct
7 Correct 299 ms 123636 KB Output is correct
8 Correct 308 ms 123636 KB Output is correct
9 Correct 271 ms 123592 KB Output is correct
10 Correct 156 ms 107944 KB Output is correct
11 Correct 276 ms 123384 KB Output is correct
12 Correct 141 ms 107924 KB Output is correct
13 Correct 510 ms 123508 KB Output is correct
14 Correct 512 ms 123596 KB Output is correct
15 Correct 377 ms 123520 KB Output is correct
16 Correct 425 ms 123584 KB Output is correct
17 Correct 188 ms 109880 KB Output is correct
18 Correct 163 ms 110080 KB Output is correct
19 Correct 448 ms 123488 KB Output is correct
20 Correct 471 ms 123628 KB Output is correct
21 Correct 526 ms 123584 KB Output is correct
22 Correct 170 ms 107752 KB Output is correct
23 Correct 255 ms 123628 KB Output is correct
24 Correct 144 ms 107740 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56692 KB Output is correct
2 Correct 31 ms 56660 KB Output is correct
3 Correct 29 ms 56656 KB Output is correct
4 Correct 35 ms 56636 KB Output is correct
5 Correct 32 ms 56652 KB Output is correct
6 Correct 36 ms 56640 KB Output is correct
7 Correct 47 ms 62900 KB Output is correct
8 Correct 48 ms 62864 KB Output is correct
9 Correct 48 ms 62820 KB Output is correct
10 Correct 50 ms 62868 KB Output is correct
11 Correct 42 ms 58580 KB Output is correct
12 Correct 36 ms 58568 KB Output is correct
13 Correct 50 ms 62856 KB Output is correct
14 Correct 48 ms 62924 KB Output is correct
15 Correct 48 ms 62832 KB Output is correct
16 Correct 35 ms 58512 KB Output is correct
17 Correct 50 ms 62884 KB Output is correct
18 Correct 36 ms 58436 KB Output is correct
19 Correct 345 ms 123456 KB Output is correct
20 Correct 370 ms 123636 KB Output is correct
21 Correct 345 ms 123504 KB Output is correct
22 Correct 349 ms 123612 KB Output is correct
23 Correct 173 ms 110000 KB Output is correct
24 Correct 145 ms 109948 KB Output is correct
25 Correct 299 ms 123636 KB Output is correct
26 Correct 308 ms 123636 KB Output is correct
27 Correct 271 ms 123592 KB Output is correct
28 Correct 156 ms 107944 KB Output is correct
29 Correct 276 ms 123384 KB Output is correct
30 Correct 141 ms 107924 KB Output is correct
31 Correct 510 ms 123508 KB Output is correct
32 Correct 512 ms 123596 KB Output is correct
33 Correct 377 ms 123520 KB Output is correct
34 Correct 425 ms 123584 KB Output is correct
35 Correct 188 ms 109880 KB Output is correct
36 Correct 163 ms 110080 KB Output is correct
37 Correct 448 ms 123488 KB Output is correct
38 Correct 471 ms 123628 KB Output is correct
39 Correct 526 ms 123584 KB Output is correct
40 Correct 170 ms 107752 KB Output is correct
41 Correct 255 ms 123628 KB Output is correct
42 Correct 144 ms 107740 KB Output is correct
43 Runtime error 199 ms 204612 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -