oj.uz

답안 #469408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469408 2021-08-31T22:16:55 Z aZvezda Examination (JOI19_examination) C++14
0 / 100
 3000 ms 28120 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 311 ms 4392 KB Output is correct
8 Correct 305 ms 4376 KB Output is correct
9 Correct 318 ms 4444 KB Output is correct
10 Correct 846 ms 4144 KB Output is correct
11 Correct 319 ms 4420 KB Output is correct
12 Incorrect 16 ms 988 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3063 ms 28120 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 311 ms 4392 KB Output is correct
8 Correct 305 ms 4376 KB Output is correct
9 Correct 318 ms 4444 KB Output is correct
10 Correct 846 ms 4144 KB Output is correct
11 Correct 319 ms 4420 KB Output is correct
12 Incorrect 16 ms 988 KB Output isn't correct
13 Halted 0 ms 0 KB -