Submission #1049635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049635		QuangBui	Meteors (POI11_met)	C++14	0 / 100	25 ms	65536 KiB

met

// Persia's code
#include <bits/stdc++.h>
#define bit(i, x) (x >> i & 1)
#define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 3e5 + 3;
template<typename T> void cmax(T &a, T b) {a = max(a, b);}


int n, m, k;
vector<int> a[N];
int b[N];
tuple<int, int, int> q[N];

long long bit[N];
int L[N], R[N], ans[N];
stack<int> qq[N];

void update(int x, int d) {
    for(int i = x; i <= m; i += (i & -i)) {
        bit[i] += d;
    }
}

long long get(int x) {
    long long sum = 0;
    for(int i = x; i; i -= (i & -i)) {
        sum += bit[i];
    }
    return sum;
}

void update(int l, int r, int w) {
    if (l <= r) {
        update(l, w);
        update(r + 1, -w);
    }
    else {
        update(l, w);
        update(1, w);
        update(r + 1, -w);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        a[x].push_back(i);
    }
    for(int i = 1; i <= n; i++) cin >> b[i];
    cin >> k;
    for(int i = 1; i <= k; i++) {
        int l, r, w; cin >> l >> r >> w;
        q[i] = make_tuple(l, r, w);
    }

    for(int i = 1; i <= n; i++) {
        L[i] = 1, R[i] = k, ans[i] = -1;
    }

    bool flag = 1;
    while (flag) {
        flag = 0;
        for(int i = 1; i <= n; i++) {
            if (L[i] <= R[i]) {
                int mid = (L[i] + R[i]) >> 1;
                qq[mid].push(i);
            }
        }
        for(int i = 1; i <= k; i++) {
            update(get<0>(q[i]), get<1>(q[i]), get<2>(q[i]));
            while (!qq[i].empty()) {
                flag = 1;
                int u = qq[i].top();
                qq[i].pop();

                long long sum = 0;
                for(auto x : a[u]) {
                    sum += get(x);
                    if (sum >= b[u]) break;
                }
                if (sum >= b[u]) ans[u] = i, R[u] = i - 1;
                else L[u] = i + 1;
            }
        }
        for(int i = 1; i <= m; i++) bit[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        if (ans[i] == -1) cout << "NIE";
        else cout << ans[i];
        cout << "\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