oj.uz

답안 #469409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469409 2021-08-31T22:18:03 Z aZvezda Examination (JOI19_examination) C++14
0 / 100
 1652 ms 124328 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 = 1e5 + 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 * 2];

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

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

    //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;
        if(getCnt(tree[curr], val) != 0) {
            traverse(tree[curr], 0);
        }
        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

examination.cpp: In constructor 'Node::Node(ll, Node*, Node*)':
examination.cpp:25:8: warning: 'Node::sz' will be initialized after [-Wreorder]
   25 |     ll sz, cnt;
      |        ^~
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), sz(sz), l(l), r(r) {
      |     ^~~~
examination.cpp:28:5: warning: 'Node::sz' is initialized with itself [-Winit-self]
examination.cpp:29:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   29 |         this->prior = rand() + rand() << 16ll;
      |                       ~~~~~~~^~~~~~~~
examination.cpp: In constructor 'Node::Node(ll, Node*, Node*)':
examination.cpp:28:71: warning: '*<unknown>.Node::sz' is used uninitialized in this function [-Wuninitialized]
   28 |     Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), sz(sz), l(l), r(r) {
      |                                                                       ^~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 28 ms 4368 KB Output is correct
8 Correct 28 ms 4404 KB Output is correct
9 Correct 28 ms 4396 KB Output is correct
10 Correct 28 ms 4152 KB Output is correct
11 Correct 28 ms 4404 KB Output is correct
12 Incorrect 11 ms 988 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1652 ms 124328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1652 ms 124328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 28 ms 4368 KB Output is correct
8 Correct 28 ms 4404 KB Output is correct
9 Correct 28 ms 4396 KB Output is correct
10 Correct 28 ms 4152 KB Output is correct
11 Correct 28 ms 4404 KB Output is correct
12 Incorrect 11 ms 988 KB Output isn't correct
13 Halted 0 ms 0 KB -