Submission #202241

#	Time	Username	Problem	Language	Result	Execution time	Memory
202241		himyu	새로운 문제 (POI11_met)	C++17	0 / 100	55 ms	65540 KiB

met

#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:
    i64 v;
    int l, r;

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

    Node(i64 _v) {
        v = _v;
        l = r = 0;
    }

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

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

vector<int> v;

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

int update(int s, int e, int h, const int t, const i64 d) {
    if (t < s || e < t) return h;

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

    return sz++;
}

i64 query(int s, int e, int h, const int l, const int r) {
    if (r < s || e < l)
        return 0;
    else if (l <= s && e <= r)
        return seg[h].v;
    else
        return query(s, (s + e) / 2, seg[h].l, l, r) +
               query((s + e) / 2 + 1, e, 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(1, M, PST::v[i - 1], l, d));
            if (r != M) PST::v[i] = PST::update(1, M, PST::v[i], r + 1, -d);
        } else {
            swap(l, r);
            PST::v.emplace_back(PST::update(1, M, PST::v[i - 1], 1, d));
            PST::v[i] = PST::update(1, M, PST::v[i], l + 1, -d);
            PST::v[i] = PST::update(1, M, 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(1, M, 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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13