oj.uz

Submission #532714

# Submission time Handle Problem Language Result Execution time Memory
532714 2022-03-03T16:47:58 Z Ai7081 Meteors (POI11_met) C++17
100 / 100
 2476 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
#define long long long

const int N = 300005;

int n, m, q, l[N], r[N], a[N], b[N];
long want[N], fen[N], val[N];
vector<int> own[N], check[N];

void add(int i, int val) {
    for (; i<=m; i+=i&(-i)) fen[i] += val;
    return;
}

long sum(int i) {
    long ret = 0;
    for (; i>0; i-=i&(-i)) ret += fen[i];
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int x;
        cin >> x;
        own[x].push_back(i);
    }
    for (int i=1; i<=n; i++) cin >> want[i];
    cin >> q;
    for (int i=1; i<=q; i++) cin >> a[i] >> b[i] >> val[i];
    fill_n(l, N, 1);
    fill_n(r, N, q+1);
    int time = 20;
    while (time--) {
        fill_n(check, N, vector<int>());
        for (int i=1; i<=n; i++) {
            if (l[i] < r[i]) check[(l[i]+r[i])/2].push_back(i);
        }
        fill_n(fen, N, 0);
        for (int i=1; i<=q; i++) {
            if (a[i] <= b[i]) add(a[i], val[i]), add(b[i]+1, -val[i]);
            else add(1, val[i]), add(b[i]+1, -val[i]), add(a[i], val[i]);
            for (auto j : check[i]) {
                long nowsum = 0;
                for (auto area : own[j]) nowsum += sum(area), nowsum = min(nowsum, (long)1e9);
                if (nowsum >= want[j]) r[j] = i;
                else l[j] = i+1;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if (l[i] == q+1) cout << "NIE" << endl;
        else cout << l[i] << endl;
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 19148 KB Output is correct
2 Correct 29 ms 19148 KB Output is correct
3 Correct 38 ms 19148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19144 KB Output is correct
2 Correct 28 ms 19140 KB Output is correct
3 Correct 28 ms 19148 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 20632 KB Output is correct
2 Correct 196 ms 22600 KB Output is correct
3 Correct 180 ms 22340 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 21660 KB Output is correct
2 Correct 190 ms 21768 KB Output is correct
3 Correct 222 ms 22872 KB Output is correct
4 Correct 120 ms 20932 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 21080 KB Output is correct
2 Correct 187 ms 23084 KB Output is correct
3 Correct 96 ms 19908 KB Output is correct
4 Correct 176 ms 22708 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 20200 KB Output is correct
2 Correct 197 ms 21700 KB Output is correct
3 Correct 128 ms 20572 KB Output is correct
4 Correct 208 ms 23852 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1300 ms 37044 KB Output is correct
2 Correct 945 ms 25224 KB Output is correct
3 Correct 333 ms 25408 KB Output is correct
4 Correct 2186 ms 64112 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1324 ms 35812 KB Output is correct
2 Correct 866 ms 25220 KB Output is correct
3 Correct 324 ms 25868 KB Output is correct
4 Correct 2476 ms 65536 KB Output is correct