Submission #869744

#	Time	Username	Problem	Language	Result	Execution time	Memory
869744		riariti	Meteors (POI11_met)	C++17	0 / 100	6064 ms	5468 KiB

met

// #include <bits/stdc++.h>

// #ifdef local
// #include "../../local.hpp"
// #else
// #define dbg(...)
// #endif

// using i64 = long long;
// #define int i64

// constexpr int MXN = 3E5 + 9;

// int n, m;
// int o[MXN] = {};
// int p[MXN] = {};

// int k;
// int l[MXN] = {};
// int r[MXN] = {};
// int a[MXN] = {};

// int lo[MXN] = {};
// int hi[MXN] = {};

// i64 t[MXN * 4] = {};

// void build(int v, int l, int r) {
//     t[v] = 0;
//     if (l == r) {
//         t[v] = 0;
//         return;
//     }

//     int mid = (l + r) / 2;

//     build(v + v, l, mid);
//     build(v + v + 1, mid + 1, r);
// }
// void upd(int v, int l, int r, int ql, int qr, i64 x) {
//     if (ql <= l && r <= qr) {
//         t[v] += x;
//         return;
//     }
//     if (ql > r || qr < l) {
//         return;
//     }

//     int mid = (l + r) / 2;

//     upd(v + v, l, mid, ql, qr, x);
//     upd(v + v + 1, mid + 1, r, ql, qr, x);
// }
// i64 get(int v, int l, int r, int pos, i64 sum) {
//     sum += t[v];
//     if (l == r) {
//         return sum;
//     }

//     int mid = (l + r) / 2;

//     if (pos <= mid) {
//         return get(v + v, l, mid, pos, sum);
//     } else {
//         return get(v + v + 1, mid + 1, r, pos, sum);
//     }
// }

// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     std::cin.tie(nullptr), std::cout.tie(nullptr);

//     std::cin >> n >> m;
//     for (int i = 1; i <= m; i++) {
//         std::cin >> o[i];
//     }
//     for (int i = 1; i <= n; i++) {
//         std::cin >> p[i];
//     }
//     std::cin >> k;
//     for (int i = 1; i <= k; i++) {
//         std::cin >> l[i] >> r[i] >> a[i];
//     }

//     for (int i = 0; i <= n; i++) {
//         lo[i] = 1;
//         hi[i] = k + 1;
//     }

//     std::map<int, std::vector<int>> ow;
//     for (int i = 1; i <= m; i++) {
//         ow[o[i]].push_back(i);
//     }

//     bool chk = true;
//     std::map<int, std::set<int>> wrk;
//     while (chk) {
//         chk = false;

//         build(1, 1, m);

//         for (int i = 1; i <= n; i++) {
//             if (lo[i] == hi[i]) {
//                 continue;
//             }

//             int m = (lo[i] + hi[i]) / 2;
//             wrk[m].insert(i);
//         }

//         for (int q = 1; q <= k; q++) {
//             if (l[q] <= r[q]) {
//                 upd(1, 1, m, l[q], r[q], a[q]);
//             } else {
//                 upd(1, 1, m, 1, r[q], a[q]);
//                 upd(1, 1, m, l[q], m, a[q]);
//             }

//             for (auto x : wrk[q]) {
//                 chk = true;

//                 i64 su = 0;
//                 for (auto pls : ow[x]) {
//                     su += get(1, 1, m, pls, 0);

//                     if (su >= p[x]) {
//                         break;
//                     }
//                 }

//                 if (su >= p[x]) {
//                     hi[x] = q;
//                 } else {
//                     lo[x] = q + 1;
//                 }
//             }
//         }

//         for (int i = 1; i <= k; i++) {
//             wrk[i].clear();
//         }
//     }

//     for (int i = 1; i <= n; i++) {
//         if (lo[i] <= k) {
//             std::cout << lo[i] << "\n";
//         } else {
//             std::cout << "NIE\n";
//         }
//     }

//     return 0;
// }

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 N = 3E3 + 5;

int z[N], x[N];
i64 b[N], c[N];
pair<int, int> lohi[N];
set<int> wrk[N];
vector<int> rg[N];

i64 t[4 * N];
void build(int v, int l, int r) {
    t[v] = 0;
    if (l == r) {
        t[v] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
}
void upd(int v, int l, int r, int ql, int qr, i64 x) {
    if (ql <= l && r <= qr) {
        t[v] += x;
        return;
    }
    if (ql > r || qr < l)
        return;
    int mid = (l + r) / 2;
    upd(v + v, l, mid, ql, qr, x);
    upd(v + v + 1, mid + 1, r, ql, qr, x);
}
i64 get(int v, int l, int r, int pos, i64 sum) {
    sum += t[v];
    if (l == r)
        return sum;
    int mid = (l + r) / 2;
    if (pos <= mid)
        return get(v + v, l, mid, pos, sum);
    else
        return get(v + v + 1, mid + 1, r, pos, sum);
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u;
        cin >> u;
        rg[u].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> z[i] >> x[i] >> c[i];
    }

    for (int i = 1; i <= n; i++) {
        lohi[i] = {1, q + 1};
    }

    bool chk = true;
    while (chk) {
        chk = false;
        build(1, 1, m);

        for (int i = 1; i <= n; i++) {
            int md = (lohi[i].first + lohi[i].second) / 2;
            wrk[md].insert(i);
        }

        for (int i = 1; i <= q; i++) {
            if (z[i] <= x[i]) {
                upd(1, 1, m, z[i], x[i], c[i]);
            } else {
                upd(1, 1, m, 1, x[i], c[i]);
                upd(1, 1, m, z[i], m, c[i]);
            }

            for (int to : wrk[i]) {
                chk = true;
                i64 sum = 0;

                for (int d : rg[to]) {
                    sum += get(1, 1, m, d, 0);

                    if (sum >= b[to]) {
                        break;
                    }
                }

                if (sum >= b[to]) {
                    lohi[to].second = i;
                } else {
                    lohi[to].first = i + 1;
                }
            }
        }

        for (int i = 1; i <= q; i++) {
            wrk[i].clear();
        }
    }

    for (int i = 1; i <= n; i++) {
        if (lohi[i].first <= q) {
            std::cout << lohi[i].first << '\n';
        } else {
            std::cout << "NIE\n";
        }
    }
}

• 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