oj.uz

답안 #518336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518336 2022-01-23T12:27:33 Z PiejanVDC 사탕 분배 (IOI21_candies) C++17
11 / 100
 5000 ms 2097156 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int64_t>>st;

int l,r;
int64_t lim;

int64_t query(int i, int j, int p) {
    if(i > l || j < l)
        assert(0);
    if(i == j) {
        int64_t ans = 0;
        for(auto z : st[p]) {
            if(z > 0) {
                ans += min(z, lim - ans);
            } else ans -= min(-z, ans);
        }
        return ans;
    }
    int mid = (i+j)/2;
    int64_t ans = (i <= l && mid >= l ? query(i,mid,2*p) : query(mid+1,j,2*p+1));
    for(auto z : st[p]) {
        if(z > 0) {
            ans += min(z, lim - ans);
        } else ans -= min(-z, ans);
    }
    return ans;
}

int64_t val;

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        int64_t app = val;
        while(!st[p].empty()) {
            if((st[p].back() >= 0 && app >= 0) || (st[p].back() <= 0 && app <= 0))
                app += st[p].back(),st[p].pop_back();
            else break;
        }
        st[p].push_back(app);
        return;
    }
    for(auto z : st[p])
        st[2*p].push_back(z),st[2*p+1].push_back(z);
    st[p].clear();
    int mid = (i+j)/2;
    update(i,mid,2*p),update(mid+1,j,2*p+1);
}

vector<int> distribute_candies(vector<int> c, vector<int> le, vector<int> ri, vector<int> v) {
    const int n = (int)c.size();
    const int q = (int)v.size();
    st.resize(8*n);
    for(int i = 0 ; i < q ; i++) {
        val = v[i];
        l = le[i], r = ri[i];
        update(0, n-1, 1);
    }
    vector<int>ans;
    for(int i = 0 ; i < n ; i++) {
        lim = c[i];
        l = i;
        ans.push_back(query(0,n-1,1));
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 15 ms 11724 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2378 ms 963448 KB Output is correct
2 Correct 2480 ms 960740 KB Output is correct
3 Correct 2401 ms 967056 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1676 ms 801104 KB Output is correct
3 Correct 327 ms 146892 KB Output is correct
4 Runtime error 1591 ms 2097156 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 367 ms 7792 KB Output is correct
4 Correct 409 ms 41312 KB Output is correct
5 Execution timed out 5084 ms 46612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 15 ms 11724 KB Output is correct
6 Correct 2378 ms 963448 KB Output is correct
7 Correct 2480 ms 960740 KB Output is correct
8 Correct 2401 ms 967056 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1676 ms 801104 KB Output is correct
11 Correct 327 ms 146892 KB Output is correct
12 Runtime error 1591 ms 2097156 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -