Submission #202239

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202239	2020-02-14T11:56:42 Z	himyu	Meteors (POI11_met)	C++17	24 / 100	208 ms	65540 KB

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

template <class T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

class Node {
   public:
    int s, e;
    i64 v;
    Node *l, *r;

    Node() {
        s = e = v = 0;
        l = r = nullptr;
    }

    Node(int _s, int _e, i64 _v) {
        s = _s, e = _e, v = _v;
        l = r = nullptr;
    }

    Node(int _s, int _e, i64 _v, Node* _l, Node* _r) {
        s = _s, e = _e, v = _v;
        l = _l, r = _r;
    }
};

namespace PST {
Node* init(int s, int e) {
    if (s == e)
        return new Node(s, e, 0);
    else
        return new Node(s, e, 0, init(s, (s + e) / 2),
                        init((s + e) / 2 + 1, e));
}

Node* update(Node* h, const int t, const i64 d, bool discard = false) {
    auto s = h->s, e = h->e;
    if (t < s || e < t)
        return h;
    else if (s == e) {
        auto v = h->v;
        if (discard) delete h;
        return new Node(s, e, h->v + d);
    } else {
        auto l = update(h->l, t, d);
        auto r = update(h->r, t, d);
        if (discard) delete h;
        return new Node(s, e, l->v + r->v, l, r);
    }
}

i64 query(Node* h, const int l, const int r) {
    auto s = h->s, e = h->e;
    if (r < s || e < l)
        return 0;
    else if (s == e)
        return h->v;
    else
        return query(h->l, l, r) + query(h->r, l, r);
}
}  // namespace PST

vector<Node*> seg;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> team(N + 1);
    for (int i = 1; i <= M; i++) {
        int k;
        cin >> k;
        team[k].emplace_back(i);
    }

    vector<i64> goal(N + 1);
    for (int i = 1; i <= N; i++) cin >> goal[i];

    seg.emplace_back(PST::init(1, M));

    int Q;
    cin >> Q;

    for (int i = 1; i <= Q; i++) {
        int l, r;
        i64 d;
        cin >> l >> r >> d;

        if (l <= r) {
            seg.emplace_back(PST::update(seg.back(), l, d));
            if (r != M) seg[i] = PST::update(seg[i], r + 1, -d);
        } else {
            swap(l, r);
            seg.emplace_back(PST::update(seg.back(), 1, d));
            seg[i] = PST::update(seg[i], l + 1, -d);
            seg[i] = PST::update(seg[i], r, d);
        }
    }

    for (int i = 1; i <= N; i++) {
        int s = 1, e = Q + 1;
        while (s < e) {
            int m = (s + e) / 2;

            i64 q = 0;
            for (auto el : team[i]) q += PST::query(seg[m], 1, el);

            if (q < goal[i])
                s = m + 1;
            else
                e = m;
        }

        if (s == Q + 1)
            cout << "NIE";
        else
            cout << s;
        cout << '\n';
    }

    return 0;
}

Compilation message

met.cpp: In function 'Node* PST::update(Node*, int, i64, bool)':
met.cpp:58:14: warning: unused variable 'v' [-Wunused-variable]
         auto v = h->v;
              ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	1656 KB	Output is correct
2	Correct	40 ms	1784 KB	Output is correct
3	Correct	42 ms	1784 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	1656 KB	Output is correct
2	Correct	45 ms	1724 KB	Output is correct
3	Correct	44 ms	1784 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	155 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	152 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	105 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	150 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	208 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	198 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-