oj.uz

답안 #591494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591494 2022-07-07T14:03:56 Z Lucpp 사탕 분배 (IOI21_candies) C++17
27 / 100
 401 ms 26400 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Op{
    ll add = 0, lo = -INF, hi = INF;
};
Op merge(Op a, Op b){
    Op c;
    c.add = a.add+b.add;
    a.lo += b.add;
    a.hi += b.add;
    if(b.lo > a.hi){
        c.lo = c.hi = b.lo;
    }
    else if(b.hi < a.lo){
        c.lo = c.hi = b.hi;
    }
    else{
        c.lo = max(a.lo, b.lo);
        c.hi = min(a.hi, b.hi);
    }
    return c;
}

int cap;
vector<Op> O;
vector<bool> lazy;

void apply(Op o, int i){
    O[i] = merge(O[i], o);
    lazy[i] = true;
}
void push(int i){
    if(lazy[i]){
        apply(O[i], 2*i);
        apply(O[i], 2*i+1);
        O[i] = Op();
        lazy[i] = false;
    }
}
void upd(int l, int r, Op x, int a, int b, int i){
    if(l <= a && b <= r) apply(x, i);
    else if(b < l || r < a) return;
    else{
        push(i);
        int m = (a+b)/2;
        upd(l, r, x, a, m, 2*i);
        upd(l, r, x, m+1, b, 2*i+1);
    }
}
void go(int p, int a, int b, int i){
    if(a == b) return;
    push(i);
    int m = (a+b)/2;
    if(p <= m) go(p, a, m, 2*i);
    else go(p, m+1, b, 2*i+1);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int)c.size();
    int q = (int)l.size();
    for(cap = 1; cap < n; cap *= 2);
    O.resize(2*cap);
    lazy.resize(2*cap);

    for(int i = 0; i < q; i++){
        upd(l[i]+1, r[i]+1, {v[i], 0, c[0]}, 1, cap, 1);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        go(i+1, 1, cap, 1);
        ans[i] = (int)min(O[i+cap].hi, max(O[i+cap].lo, O[i+cap].add));
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 150 ms 8120 KB Output is correct
3 Correct 95 ms 18376 KB Output is correct
4 Correct 335 ms 25644 KB Output is correct
5 Correct 374 ms 26028 KB Output is correct
6 Correct 395 ms 26400 KB Output is correct
7 Correct 401 ms 25664 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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