Submission #1172255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172255		gyg	사탕 분배 (IOI21_candies)	C++20	8 / 100	133 ms	25132 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#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<sig> distribute_candies(vec<sig> _c, vec<sig> _l, vec<sig> _r, vec<sig> _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<sig> ans;
    for (int i = 0; i < n; i++) {
        int x = sgt.qry(i);
        // ans.push_back(x);
        ans.push_back(min(x, c[i]));
    } 
    return ans;
}

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