Submission #469412

#	Time	Username	Problem	Language	Result	Execution time	Memory
469412		aZvezda	Examination (JOI19_examination)	C++14	100 / 100	2714 ms	167184 KiB

examination

#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];

void traverse(pnode x, ll tab = 0) {
    return;
    if(!x) {return;}
    traverse(x->l, tab + 1);
    for(ll i = 0; i < tab; i ++) {
        //cerr << "  ";
    }
    //cerr << "{" << x->val << "," << x->cnt << "}" << endl;
    traverse(x->r, tab + 1);
}

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);
    }

    //cerr << "Adding " << x << endl;

    //cerr << "First part" << endl;
    traverse(splt2.first);
    //cerr << "Second part" << endl;
    traverse(splt2.second);
    //cerr << "Third part" << endl;
    traverse(splt.second);

    //cerr << endl;


    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);

    //cerr << "Searching for " << x << endl;

    //cerr << "First part" << endl;
    traverse(splt.first);
    //cerr << "Second part" << endl;
    traverse(splt.second);

    //cerr << endl;

    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) {
        //cerr << "Getting count for " << curr << " " << l << " " << r << " " << ind << " " << val << " --> " << getCnt(tree[curr], val) << endl;
        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); //cerr.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;
            //cerr << "Adding " << b[ind] << " " << s[ind] << endl;
            add(1, 0, MAX_N - 1, b[ind], s[ind]);
        } else {
            ll ind = quer[i].second.second;
            //cerr << "Query " << ind << endl;
            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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57