Submission #202240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202240	2020-02-14T12:11:07 Z	himyu	Meteors (POI11_met)	C++17	0 / 100	54 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;
    int l, r;

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

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

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

namespace PST {
Node seg[5010100];
int sz = 0;

vector<int> v;

int init(int s, int e) {
    if (s == e)
        seg[sz] = Node(s, e, 0);
    else
        seg[sz] = Node(s, e, 0, init(s, (s + e) / 2), init((s + e) / 2 + 1, e));
    return sz++;
}

int update(int h, const int t, const i64 d) {
    auto s = seg[h].s, e = seg[h].e;
    if (t < s || e < t) return h;

    if (s == e)
        seg[sz] = Node(s, e, seg[h].v + d);
    else {
        auto l = update(seg[h].l, t, d);
        auto r = update(seg[h].r, t, d);
        seg[sz] = Node(s, e, seg[l].v + seg[r].v, l, r);
    }

    return sz++;
}

i64 query(int h, const int l, const int r) {
    auto s = seg[h].s, e = seg[h].e;
    if (r < s || e < l)
        return 0;
    else if (s == e)
        return seg[h].v;
    else
        return query(seg[h].l, l, r) + query(seg[h].r, l, r);
}
}  // namespace PST

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

    PST::v.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) {
            PST::v.emplace_back(PST::update(PST::v[i - 1], l, d));
            if (r != M) PST::v[i] = PST::update(PST::v[i], r + 1, -d);
        } else {
            swap(l, r);
            PST::v.emplace_back(PST::update(PST::v[i - 1], 1, d));
            PST::v[i] = PST::update(PST::v[i], l + 1, -d);
            PST::v[i] = PST::update(PST::v[i], r, d);
        }
    }

    for (int i = 1; i <= N; i++) {
        int s = 1, e = Q + 1;
        while (s < e) {
            int m = (s + e) / 2;
            auto root = PST::v[m];

            i64 q = 0;
            for (auto el : team[i]) q += PST::query(root, 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;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	51 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	50 ms	65540 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	49 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	48 ms	65540 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	54 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	49 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Submission #202240

Compilation message