oj.uz

답안 #469407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469407 2021-08-31T22:16:23 Z aZvezda Examination (JOI19_examination) C++14
0 / 100
 3000 ms 30724 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) {
    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 313 ms 4560 KB Output is correct
8 Correct 312 ms 4712 KB Output is correct
9 Correct 310 ms 4596 KB Output is correct
10 Correct 863 ms 4272 KB Output is correct
11 Correct 334 ms 4448 KB Output is correct
12 Incorrect 18 ms 968 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 30724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 30724 KB Time limit exceeded
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 313 ms 4560 KB Output is correct
8 Correct 312 ms 4712 KB Output is correct
9 Correct 310 ms 4596 KB Output is correct
10 Correct 863 ms 4272 KB Output is correct
11 Correct 334 ms 4448 KB Output is correct
12 Incorrect 18 ms 968 KB Output isn't correct
13 Halted 0 ms 0 KB -