Submission #605643

#	Time	Username	Problem	Language	Result	Execution time	Memory
605643		1ne	Meteors (POI11_met)	C++14	100 / 100	1924 ms	31728 KiB

met

#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
const int maxN = 3 << 17;
const int maxK = 1 << 10;
const int INF = (int)1e9;
typedef long long ll;
 
int o[maxN];
 
ll add[maxN];
ll need[maxN];
int start[maxN];
ll startNeed[maxN];
 
int l[maxN];
int r[maxN];
ll a[maxN];
 
vector<int> pos[maxN];
 
int main() {
    ios_base::sync_with_stdio(0);
 
    for (int i = 0; i < maxN; i++) {
        start[i] = INF;
    }
 
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> o[i];
        pos[o[i]].push_back(i);
    }
 
    for (int i = 1; i <= n; i++) {
        cin >> need[i];
    }
 
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) { // O((m + n) * q / maxK)
        cin >> l[i] >> r[i] >> a[i];
        if (l[i] > r[i]) {
            add[1] += a[i];
            add[r[i] + 1] -= a[i];
 
            add[l[i]] += a[i];
            add[m + 1] -= a[i];
        } else {
            add[l[i]] += a[i];
            add[r[i] + 1] -= a[i];
        }
        if (i % maxK == 0 || i == q) {
            ll s = 0;
            for (int j = 1; j <= m; j++) {
                s += add[j];
                add[j] = 0;
                need[o[j]] -= s;
            }
            for (int j = 1; j <= n; j++) {
                if (start[j] == INF && need[j] <= 0) {
                    startNeed[j] = need[j];
                    start[j] = i;
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) { // O((m + n) * maxK)
        if (start[i] == INF) {
            cout << "NIE" << endl;
            continue;
        }
        int j = start[i];
        ll s = startNeed[i];
        while (s <= 0 && j > 0) {
            for (int ii = 0; ii < (int)pos[i].size(); ii++) {
                int x = pos[i][ii];
                if (l[j] > r[j] && (x >= l[j] || x <= r[j])) {
                    s += a[j];
                }
                if (l[j] <= r[j] && (x >= l[j] && x <= r[j])) {
                    s += a[j];
                }
            }
            j--;
        }
        cout << j + 1 << endl;
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13