제출 #1172248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172248		gyg	사탕 분배 (IOI21_candies)	C++20	0 / 100	131 ms	22296 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector 
const int N = 2e5 + 5;

int n;
arr<int, N> c;
vec<vec<int>> q;

struct Sgt {
    arr<int, 4 * N> tr;
    void upd(int l, int r, int x, int u = 1, int lw = 0, int hg = n - 1) {
        if (l <= lw && hg <= r) { tr[u] += x; return; }
        int md = (lw + hg) / 2;
        if (l <= md) upd(l, r, x, 2 * u, lw, md);
        if (r > md) upd(l, r, x, 2 * u + 1, md + 1, hg);        
    }
    int qry(int i, int u = 1, int lw = 0, int hg = n - 1) {
        if (lw == hg) return tr[u];
        int md = (lw + hg) / 2;
        if (i <= md) return tr[u] + qry(i, 2 * u, lw, md);
        else return tr[u] + qry(i, 2 * u + 1, md + 1, hg);
    }
} sgt;

vec<int> distribute_candies(vec<int> _c, vec<int> _l, vec<int> _r, vec<int> _x) {
    n = _c.size();
    for (int i = 0; i < n; i++) c[i] = _c[i];
    for (int i = 0; i < _l.size(); i++) {
        int l = _l[i], r = _r[i], x = _x[i];
        q.push_back({l, r, x});
    }

    for (vec<int> x : q)
        sgt.upd(x[0], x[1], x[2]);
    
    vec<int> ans;
    for (int i = 0; i < n; i++) {
        int x = sgt.qry(i);
        ans.push_back(min(x, c[i]));
    } 
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33