oj.uz

답안 #496738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
496738 2021-12-22T03:45:12 Z Nalrimet Meteors (POI11_met) C++17
74 / 100
 354 ms 56600 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define left(v) v + v
#define right(v) v + v + 1

using namespace std;

typedef long long ll;

const ll N = (ll) 3e5 + 17;
const ll M = (ll) 5e3 + 69;

int zxc = 1, n, m, q, a[N];
ll x[N], upd[N];
int l[N], r[N];
int p[N], cur[N], ql[N], qr[N];

vector<int> v[N], vq[N];

ll get(int v, int tl, int tr, int pos) {
    if(tl == tr) return upd[v];
    int tm = (tl + tr) / 2;
    if(pos <= tm) return get(left(v), tl, tm, pos) + upd[v];
    else return get(right(v), tm + 1, tr, pos) + upd[v];
}

void update(int v, int tl, int tr, int ql, int qr, ll val) {
    if(tr < ql || qr < tl) return;
    if(ql <= tl && tr <= qr){
		upd[v] += val;
        return;
    }
    int mid = (tl + tr) / 2;
    update(left(v), tl, mid, ql, qr, val);
    update(right(v), mid + 1, tr, ql, qr, val);
}

 main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        cin >> p[i];
        v[p[i]].pb(i);
    }

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> q;

    for(int i = 1; i <= n; i++)
        ql[i] = 1, qr[i] = q + 1;

    for(int i = 1; i <= q; i++)
        cin >> l[i] >> r[i] >> x[i];

    int ok = 1;
    while(ok){
        ok = 0;
        memset(upd, 0, sizeof(upd));
        for(int i = 1; i <= n; i++)
            if(ql[i] != qr[i])
                vq[(ql[i] + qr[i]) / 2].pb(i);

        for(int i = 1; i <= q; i++){
            if(l[i] <= r[i])
                update(1, 1, m, l[i], r[i], x[i]);
            else update(1, 1, m, l[i], m, x[i]), update(1, 1, m, 1, r[i], x[i]);
            for(int id : vq[i]){
                ok = 1;
                ll sum = 0;
                for(int x : v[id]) {
                    sum += get(1, 1, m, x);
                    if(sum >= a[id]) break;
                }
                if(sum >= a[id]) qr[id] = i;
                else ql[id] = i + 1;
            }
          	vq[i].clear();
        }
    }

    for(int i = 1; i <= n; i++) {
        if(ql[i] == q + 1) cout << "NIE\n";
        else cout << ql[i] << '\n';
    }
}

Compilation message

met.cpp:43:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |  main() {
      |  ^~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 11 ms 16844 KB Output is correct
3 Correct 12 ms 16844 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16836 KB Output is correct
2 Correct 12 ms 16856 KB Output is correct
3 Correct 13 ms 16880 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 18500 KB Output is correct
2 Correct 350 ms 20440 KB Output is correct
3 Correct 345 ms 20136 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 19524 KB Output is correct
2 Correct 354 ms 19576 KB Output is correct
3 Correct 334 ms 20600 KB Output is correct
4 Correct 73 ms 18752 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 18960 KB Output is correct
2 Correct 245 ms 21008 KB Output is correct
3 Correct 148 ms 17576 KB Output is correct
4 Correct 336 ms 20576 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 18080 KB Output is correct
2 Correct 289 ms 19600 KB Output is correct
3 Correct 312 ms 18412 KB Output is correct
4 Correct 351 ms 21804 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 56600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 140 ms 55760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -