oj.uz

Submission #469414

# Submission time Handle Problem Language Result Execution time Memory
469414 2021-08-31T22:23:52 Z aZvezda Examination (JOI19_examination) C++14
100 / 100
 2759 ms 162504 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 2e6 + 10;
ll a[MAX_N], b[MAX_N], s[MAX_N];
ll n, q;
ll x[MAX_N], y[MAX_N], z[MAX_N];
ll ans[MAX_N];

pair<ll, pair<ll, ll> > quer[MAX_N];

struct Node {
    Node *l, *r;
    ll val;
    ll sz, cnt;
    ll prior;

    Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), l(l), r(r) {
        this->prior = rand() + rand() << 16ll;
        this->cnt = 1;
        this->sz = 1;
    }
};

typedef Node* pnode;

pnode tree[4 * MAX_N];

ll size(pnode x) {
    if(!x) {
        return 0;
    } else {
        return x->sz;
    }
}

void pull(pnode x) {
    if(!x) {return;}
    x->sz = size(x->l) + size(x->r) + x->cnt;
}

pnode merge(pnode l, pnode r) {
    if(!l) {return r;}
    if(!r) {return l;}

    if(l->prior > r->prior) {
        l->r = merge(l->r, r);
        pull(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        pull(r);
        return r;
    }
}

pair<pnode, pnode> split(pnode t, ll x) {
    if(!t) {return {nullptr, nullptr};}
    if(t->val <= x) {
        auto rec = split(t->r, x);
        t->r = rec.first;
        pull(t);
        return {t, rec.second};
    } else {
        auto rec = split(t->l, x);
        t->l = rec.second;
        pull(t);
        return {rec.first, t};
    }
}

void insert(pnode &t, ll x) {
    auto splt = split(t, x);
    auto splt2 = split(splt.first, x - 1);

    if(!splt2.second) {
        splt2.second = new Node(x);
    } else {
        splt2.second->cnt ++;
        pull(splt2.second);
    }

    auto trp1 = merge(splt2.first, splt2.second);
    auto trp = merge(trp1, splt.second);

    t = trp;
}

ll getCnt(pnode &t, ll x) {
    auto splt = split(t, x - 1);

    ll ret = size(splt.second);

    t = merge(splt.first, splt.second);

    return ret;
}

void add(ll curr, ll l, ll r, ll ind, ll val) {
    if(ind < l || ind > r) {
        return;
    }
    insert(tree[curr], val);

    if(l == r) {return;}
    ll m = (l + r) / 2ll;
    add(curr * 2, l, m, ind, val);
    add(curr * 2 + 1, m + 1, r, ind, val);
}

ll cnt(ll curr, ll l, ll r, ll ind, ll val) {
    if(ind <= l) {
        return getCnt(tree[curr], val);
    } else if(ind > r) {
        return 0;
    }
    ll m = (l + r) / 2ll;
    return cnt(curr * 2, l, m, ind, val) + cnt(curr * 2 + 1, m + 1, r, ind, val);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector<ll> c;
    cin >> n >> q;
    for(ll i = 0; i < n; i ++) {
        cin >> a[i] >> b[i];
        s[i] = a[i] + b[i];
        c.push_back(a[i]);
        c.push_back(b[i]);
        c.push_back(s[i]);
    }
    for(ll i = 0; i < q; i ++) {
        cin >> x[i] >> y[i] >> z[i];
        c.push_back(x[i]);
        c.push_back(y[i]);
        c.push_back(z[i]);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());

    for(ll i = 0; i < n; i ++) {
        a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
        b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
        s[i] = lower_bound(c.begin(), c.end(), s[i]) - c.begin();
        quer[i] = {a[i], {1, i}};
    }

    for(ll i = 0; i < q; i ++) {
        x[i] = lower_bound(c.begin(), c.end(), x[i]) - c.begin();
        y[i] = lower_bound(c.begin(), c.end(), y[i]) - c.begin();
        z[i] = lower_bound(c.begin(), c.end(), z[i]) - c.begin();
        quer[n + i] = {x[i], {-1, i}};
    }
    sort(quer, quer + n + q);

    for(ll i = n + q - 1; i >= 0; i --) {
        if(quer[i].second.first == 1) {
            ll ind = quer[i].second.second;
            add(1, 0, MAX_N - 1, b[ind], s[ind]);
        } else {
            ll ind = quer[i].second.second;
            ans[ind] = cnt(1, 0, MAX_N - 1, y[ind], z[ind]);
        }
    }

    for(ll i = 0; i < q; i ++) {
        cout << ans[i] << endl;
    }

    return 0;
}

Compilation message

examination.cpp: In constructor 'Node::Node(ll, Node*, Node*)':
examination.cpp:24:8: warning: 'Node::val' will be initialized after [-Wreorder]
   24 |     ll val;
      |        ^~~
examination.cpp:23:11: warning:   'Node* Node::l' [-Wreorder]
   23 |     Node *l, *r;
      |           ^
examination.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), l(l), r(r) {
      |     ^~~~
examination.cpp:29:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   29 |         this->prior = rand() + rand() << 16ll;
      |                       ~~~~~~~^~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 34 ms 5260 KB Output is correct
8 Correct 33 ms 5268 KB Output is correct
9 Correct 35 ms 5288 KB Output is correct
10 Correct 28 ms 5028 KB Output is correct
11 Correct 35 ms 5148 KB Output is correct
12 Correct 12 ms 1048 KB Output is correct
13 Correct 32 ms 5280 KB Output is correct
14 Correct 32 ms 5308 KB Output is correct
15 Correct 34 ms 5372 KB Output is correct
16 Correct 34 ms 5144 KB Output is correct
17 Correct 22 ms 5112 KB Output is correct
18 Correct 5 ms 1076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2440 ms 143816 KB Output is correct
2 Correct 2625 ms 144576 KB Output is correct
3 Correct 2243 ms 144640 KB Output is correct
4 Correct 1032 ms 109712 KB Output is correct
5 Correct 2471 ms 111832 KB Output is correct
6 Correct 355 ms 16968 KB Output is correct
7 Correct 2355 ms 144596 KB Output is correct
8 Correct 2238 ms 144548 KB Output is correct
9 Correct 2258 ms 144468 KB Output is correct
10 Correct 2276 ms 104744 KB Output is correct
11 Correct 852 ms 103784 KB Output is correct
12 Correct 164 ms 16376 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2440 ms 143816 KB Output is correct
2 Correct 2625 ms 144576 KB Output is correct
3 Correct 2243 ms 144640 KB Output is correct
4 Correct 1032 ms 109712 KB Output is correct
5 Correct 2471 ms 111832 KB Output is correct
6 Correct 355 ms 16968 KB Output is correct
7 Correct 2355 ms 144596 KB Output is correct
8 Correct 2238 ms 144548 KB Output is correct
9 Correct 2258 ms 144468 KB Output is correct
10 Correct 2276 ms 104744 KB Output is correct
11 Correct 852 ms 103784 KB Output is correct
12 Correct 164 ms 16376 KB Output is correct
13 Correct 2661 ms 144608 KB Output is correct
14 Correct 2413 ms 144636 KB Output is correct
15 Correct 2352 ms 144524 KB Output is correct
16 Correct 1205 ms 109712 KB Output is correct
17 Correct 2759 ms 112224 KB Output is correct
18 Correct 373 ms 16788 KB Output is correct
19 Correct 2646 ms 144608 KB Output is correct
20 Correct 2451 ms 144716 KB Output is correct
21 Correct 2709 ms 144476 KB Output is correct
22 Correct 2219 ms 104868 KB Output is correct
23 Correct 859 ms 103120 KB Output is correct
24 Correct 162 ms 16164 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 34 ms 5260 KB Output is correct
8 Correct 33 ms 5268 KB Output is correct
9 Correct 35 ms 5288 KB Output is correct
10 Correct 28 ms 5028 KB Output is correct
11 Correct 35 ms 5148 KB Output is correct
12 Correct 12 ms 1048 KB Output is correct
13 Correct 32 ms 5280 KB Output is correct
14 Correct 32 ms 5308 KB Output is correct
15 Correct 34 ms 5372 KB Output is correct
16 Correct 34 ms 5144 KB Output is correct
17 Correct 22 ms 5112 KB Output is correct
18 Correct 5 ms 1076 KB Output is correct
19 Correct 2440 ms 143816 KB Output is correct
20 Correct 2625 ms 144576 KB Output is correct
21 Correct 2243 ms 144640 KB Output is correct
22 Correct 1032 ms 109712 KB Output is correct
23 Correct 2471 ms 111832 KB Output is correct
24 Correct 355 ms 16968 KB Output is correct
25 Correct 2355 ms 144596 KB Output is correct
26 Correct 2238 ms 144548 KB Output is correct
27 Correct 2258 ms 144468 KB Output is correct
28 Correct 2276 ms 104744 KB Output is correct
29 Correct 852 ms 103784 KB Output is correct
30 Correct 164 ms 16376 KB Output is correct
31 Correct 2661 ms 144608 KB Output is correct
32 Correct 2413 ms 144636 KB Output is correct
33 Correct 2352 ms 144524 KB Output is correct
34 Correct 1205 ms 109712 KB Output is correct
35 Correct 2759 ms 112224 KB Output is correct
36 Correct 373 ms 16788 KB Output is correct
37 Correct 2646 ms 144608 KB Output is correct
38 Correct 2451 ms 144716 KB Output is correct
39 Correct 2709 ms 144476 KB Output is correct
40 Correct 2219 ms 104868 KB Output is correct
41 Correct 859 ms 103120 KB Output is correct
42 Correct 162 ms 16164 KB Output is correct
43 Correct 2339 ms 161920 KB Output is correct
44 Correct 2406 ms 161904 KB Output is correct
45 Correct 2089 ms 162504 KB Output is correct
46 Correct 1176 ms 153832 KB Output is correct
47 Correct 2437 ms 159920 KB Output is correct
48 Correct 371 ms 15904 KB Output is correct
49 Correct 2342 ms 162340 KB Output is correct
50 Correct 2282 ms 161452 KB Output is correct
51 Correct 2564 ms 162396 KB Output is correct
52 Correct 2423 ms 157964 KB Output is correct
53 Correct 943 ms 153592 KB Output is correct