oj.uz

답안 #443075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443075 2021-07-09T15:31:15 Z MladenP Meteors (POI11_met) C++17
74 / 100
 1115 ms 35772 KB 
#include <bits/stdc++.h>
#define MAXN 300010
#define MAXBIN 20
#define MAXV 300000
#define lld long long
#define endl '\n'
#define PRINT(x) cerr<<flush<<#x<<'='<<x<<endl;
using namespace std;
int N, M, K, l[MAXN], r[MAXN], L[MAXN], R[MAXN], rez[MAXN];
lld bit[MAXN], p[MAXN], x[MAXN];
vector<int> sec[MAXN], q[MAXN];
void update(int idx, lld val) {
    while(idx < MAXN) {
        bit[idx] += val;
        idx += idx&-idx;
    }
}
lld query(int idx) {
    lld sum = 0;
    while(idx) {
        sum += bit[idx];
        idx -= idx&-idx;
    }
    return sum;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int o; cin >> o;
        sec[o].push_back(i);
    }
    for(int i = 1; i <= N; i++) cin >> p[i];
    cin >> K;
    for(int i = 1; i <= K; i++) {
        cin >> l[i] >> r[i] >> x[i];
    }
    for(int i = 1; i <= N; i++) {
        L[i] = 1, R[i] = K, rez[i] = K+1;
    }
    bool changed = 1;
    while(changed) {
        changed = 0;
        fill(bit, bit+MAXN, 0LL);
        for(int i = 1; i <= K+1; i++) q[i].clear();

        for(int i = 1; i <= N; i++) {
            if(L[i] <= R[i]) {
                changed = 1;
                int mid = (L[i]+R[i])/2;
                q[mid].push_back(i);
            }
        }

        for(int i = 1; i <= K; i++) {
            if(l[i] <= r[i]) {
                update(l[i], x[i]);
                update(r[i]+1, -x[i]);
            } else {
                update(1, x[i]);
                update(r[i]+1, -x[i]);
                update(l[i], x[i]);
                update(M+1, -x[i]);
            }
            for(auto x : q[i]) {
                lld sum = 0;
                for(int s : sec[x]) {
                    sum += query(s);
                }
                if(sum >= p[x]) {
                    R[x] = i-1;
                    rez[x] = i;
                } else {
                    L[x] = i+1;
                }
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        if(rez[i] == K+1) cout << "NIE" << endl;
        else cout << rez[i] << endl;
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16844 KB Output is correct
2 Correct 14 ms 16776 KB Output is correct
3 Correct 13 ms 16748 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16832 KB Output is correct
2 Correct 14 ms 16864 KB Output is correct
3 Correct 14 ms 16896 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 18288 KB Output is correct
2 Correct 176 ms 20584 KB Output is correct
3 Correct 137 ms 19980 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 19424 KB Output is correct
2 Correct 156 ms 19568 KB Output is correct
3 Correct 178 ms 20600 KB Output is correct
4 Correct 43 ms 18756 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 18788 KB Output is correct
2 Correct 179 ms 21124 KB Output is correct
3 Correct 179 ms 17728 KB Output is correct
4 Correct 135 ms 20492 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 17868 KB Output is correct
2 Correct 167 ms 19396 KB Output is correct
3 Correct 111 ms 18288 KB Output is correct
4 Correct 179 ms 21792 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1115 ms 35772 KB Output is correct
2 Incorrect 747 ms 22788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1097 ms 34484 KB Output is correct
2 Incorrect 743 ms 22780 KB Output isn't correct
3 Halted 0 ms 0 KB -