oj.uz

답안 #761641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761641 2023-06-20T06:39:24 Z vjudge1 Meteors (POI11_met) C++17
74 / 100
 322 ms 65536 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 3e5 + 100;
const ll INF = (ll)2e18;
const int inf = (ll)2e9;
const int maxl = 26;
const int MOD = 1e9 + 7;


int n, m, q, sz;
vector<int> g[maxn];
int a[maxn];
ll d[maxn * 60];
int L[maxn * 60];
int R[maxn * 60];
int root[maxn];

int copy(int v){
    int nv = ++sz;
    d[nv] = d[v];
    L[nv] = L[v];
    R[nv] = R[v];
    return nv;
}

int build(int tl = 1, int tr = m){
    int v = ++sz;
    if(tl < tr){
        int mid = (tl + tr) >> 1;
        L[v] = build(tl, mid);
        R[v] = build(mid + 1, tr);
    }
    return v;
}

int upd(int l, int r, int x, int v, int tl = 1, int tr = m){
    int nv = copy(v);
    if(tl > r || tr < l) return nv;
    if(l <= tl && tr <= r) d[nv] += x;
    else{
        int mid = (tl + tr) >> 1;
        L[nv] = upd(l, r, x, L[nv], tl, mid);
        R[nv] = upd(l, r, x, R[nv], mid+1, tr);
    }
    return nv;
}

int upd1(int l, int r, int x, int v, int tl = 1, int tr = m){
    int nv = copy(v);
    if(r < tl && tr < l) return nv;
    if(l <= tl || tr <= r) d[nv] += x;
    else{
        int mid = (tl + tr) >> 1;
        L[nv] = upd1(l, r, x, L[nv], tl, mid);
        R[nv] = upd1(l, r, x, R[nv], mid+1, tr);
    }
    return nv;
}

ll get(int i, int v, int tl = 1, int tr = m){
    if(tl == tr) return d[v];
    int mid = (tl + tr) >> 1;
    if(i <= mid) return get(i, L[v], tl, mid) + d[v];
    else return get(i, R[v], mid + 1, tr) + d[v];
}

void test(){
    cin >> n >> m;
    root[0] = build();
    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        g[x].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
        int l, r, x;
        cin >> l >> r >> x;
        if(l <= r) root[i] = upd(l, r, x, root[i-1]);
        else root[i] = upd1(l, r, x, root[i-1]);
    }
    for(int i = 1; i <= n; i++){
        int ans = -1;
        for(int l = 0, r = q; l <= r;){
            int mid = (l + r) >> 1;
            ll sum = 0;
            for(int x: g[i]){
                sum += get(x, root[mid]);
            }
            if(sum < a[i]) l = mid + 1;
            else r = mid - 1, ans = mid;
        }
        if(ans == -1) cout << "NIE\n";
        else cout << ans << ent;
    }
}

int main(){
    // freopen("cows.in", "r", stdin);
    // freopen("cows.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7788 KB Output is correct
2 Correct 6 ms 7904 KB Output is correct
3 Correct 4 ms 7904 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 52352 KB Output is correct
2 Correct 178 ms 52760 KB Output is correct
3 Correct 322 ms 52712 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 52480 KB Output is correct
2 Correct 178 ms 52520 KB Output is correct
3 Correct 182 ms 52776 KB Output is correct
4 Correct 37 ms 12384 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 32256 KB Output is correct
2 Correct 87 ms 53124 KB Output is correct
3 Correct 31 ms 30284 KB Output is correct
4 Correct 160 ms 52748 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 52332 KB Output is correct
2 Correct 154 ms 52504 KB Output is correct
3 Correct 103 ms 52324 KB Output is correct
4 Correct 175 ms 53060 KB Output is correct

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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