oj.uz

Submission #1049635

# Submission time Handle Problem Language Result Execution time Memory
1049635 2024-08-09T03:07:26 Z QuangBui Meteors (POI11_met) C++14
0 / 100
 25 ms 65536 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -