oj.uz

Submission #532706

# Submission time Handle Problem Language Result Execution time Memory
532706 2022-03-03T16:39:58 Z Ai7081 Meteors (POI11_met) C++17
74 / 100
 1344 ms 44852 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);
                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 25 ms 19148 KB Output is correct
2 Correct 32 ms 19140 KB Output is correct
3 Correct 28 ms 19148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19160 KB Output is correct
2 Correct 26 ms 19148 KB Output is correct
3 Correct 36 ms 19148 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 21452 KB Output is correct
2 Correct 197 ms 23624 KB Output is correct
3 Correct 177 ms 23264 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 22776 KB Output is correct
2 Correct 176 ms 22796 KB Output is correct
3 Correct 200 ms 23908 KB Output is correct
4 Correct 84 ms 21188 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 21912 KB Output is correct
2 Correct 182 ms 24372 KB Output is correct
3 Correct 92 ms 20476 KB Output is correct
4 Correct 190 ms 23740 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 21236 KB Output is correct
2 Correct 174 ms 22844 KB Output is correct
3 Correct 132 ms 21616 KB Output is correct
4 Correct 207 ms 25028 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1344 ms 44852 KB Output is correct
2 Incorrect 940 ms 32924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 43312 KB Output is correct
2 Incorrect 982 ms 31444 KB Output isn't correct
3 Halted 0 ms 0 KB -