oj.uz

답안 #761623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761623 2023-06-20T05:49:04 Z vjudge1 Meteors (POI11_met) C++17
0 / 100
 1217 ms 34444 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;
vector<int> g[maxn];
int a[maxn];
int l[maxn];
int r[maxn];
int c[maxn];
ll d[maxn * 4];
int used[maxn * 4];
int ans[maxn];

void clear(int v = 1, int tl = 1, int tr = m){
    if(!used[v]) return;
    used[v] = 0; d[v] = 0;
    if(tl < tr){
        int mid = (tl + tr) >> 1;
        clear(v<<1, tl, mid);
        clear(v<<1|1, mid+1, tr);
    }
}

bool ok(int l, int r, int tl, int tr){
    if(l <= r) return l <= tl && tr <= r;
    return l <= tl || tr <= r;
}

bool nt(int l, int r, int tl, int tr){
    if(l <= r) return tr < l || tl > r;
    return tr < l && tl > r;
}

void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = m){
    if(nt(l, r, tl, tr)) return;
    used[v] = 1;
    if(ok(l, r, tl, tr)) d[v] += x;
    else{
        int mid = (tl + tr) >> 1;
        upd(l, r, x, v<<1, tl, mid);
        upd(l, r, x, v<<1|1, mid+1, tr);
    }
}

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

void f(vector<int> &v, int tl = 1, int tr = n){
    if(tl == tr){
        for(int x: v){
            ll sum = 0;
            for(int i: g[x]){
                sum += ok(l[tl], r[tl], i, i) * c[tl];
            }
            if(a[x] > sum) ans[x] = -1;
            else ans[x] = tl;
        }
    } else{
        int mid = (tl + tr) >> 1;
        clear();
        for(int i = tl; i <= mid; i++){
            upd(l[i], r[i], c[i]);
        }
        vector<int> L, R;
        for(int x: v){
            ll sum = 0;
            for(int i: g[x]){
                sum += get(i);
            }
            if(sum >= a[x]) L.push_back(x);
            else a[x] -= sum, R.push_back(x);
        }
        f(L, tl, mid);
        f(R, mid + 1, tr);
    }
}

void test(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        g[x].push_back(i);
    }
    vector<int> v;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back(i);
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> r[i] >> c[i];
    }
    f(v);
    for(int i = 1; i <= n; i++){
        if(ans[i] == -1) cout << "NIE\n";
        else cout << ans[i] << 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
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Incorrect 5 ms 7508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 10180 KB Output is correct
2 Incorrect 156 ms 11956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 10544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 8944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 9796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1217 ms 34444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1054 ms 33296 KB Output isn't correct
2 Halted 0 ms 0 KB -