Submission #1055516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055516		mariaclara	Distributing Candies (IOI21_candies)	C++17	29 / 100	308 ms	29384 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

vector<int> lazy, set_c, set_0;
vector<pii> s_c, seg;

void prop(int node, int l, int r) {
    if(set_c[node]) seg[node] = {s_c[l].fr, s_c[r].fr};
    if(set_0[node]) seg[node] = {0,0};
    seg[node].fr += lazy[node];
    seg[node].sc += lazy[node];

    if(l != r) {
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
        if(set_c[node]) {
            set_c[2*node] = set_c[2*node+1] = 1;
            set_0[2*node] = set_0[2*node+1] = 0;
            lazy[2*node] = lazy[2*node+1] = lazy[node];
        }
        if(set_0[node]) {
            set_0[2*node] = set_0[2*node+1] = 1;
            set_c[2*node] = set_c[2*node+1] = 0;
            lazy[2*node] = lazy[2*node+1] = lazy[node];
        }
    }

    lazy[node] = set_0[node] = set_c[node] = 0;
}

void update(int node, int l, int r, int p, int q, bool S0, bool SC, int val) {
    prop(node, l, r);
    //cout << "update " << l << " " << r << " " << p << " " << q << " " <<  S0 << " " << SC << " " << val << "\n";
    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        set_0[node] = S0;
        set_c[node] = SC;
        lazy[node] = val;
        prop(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    update(2*node, l, mid, p, q, S0, SC, val);
    update(2*node+1, mid+1, r, p, q, S0, SC, val);
    seg[node].fr = seg[2*node].fr;
    seg[node].sc = seg[2*node+1].sc;
}

int query_minus(int node, int l, int r, int val) {
    prop(node, l, r);
    if(seg[node].fr > val) return l-1;
    if(l == r) return l;
    int mid = (l+r)/2;
    prop(2*node, l, mid);
    prop(2*node+1, mid+1, r);
    if(seg[2*node+1].fr <= val) return query_minus(2*node+1, mid+1, r, val);
    else return query_minus(2*node, l, mid, val);
}

int query_plus(int node, int l, int r, int val) {
    prop(node, l, r);
    if(seg[node].fr + val < s_c[l].fr) return l-1;
    if(l == r) return l;
    int mid = (l+r)/2;
    prop(2*node, l, mid);
    prop(2*node+1, mid+1, r);
    if(seg[2*node+1].fr + val >= s_c[mid+1].fr) return query_plus(2*node+1, mid+1, r, val);
    else return query_plus(2*node, l, mid, val);
}

int query(int node, int l, int r, int ind) {
    prop(node, l, r);
    if(l == r) return seg[node].fr;
    int mid = (l+r)/2;
    if(ind <= mid) return query(2*node, l, mid, ind);
    else return query(2*node+1, mid+1, r, ind);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = sz(c), q = sz(l);

    for(int i = 0; i < n; i++) s_c.pb({c[i], i});
    sort(all(s_c));

    seg.resize(4*n);
    lazy.resize(4*n);
    set_0.resize(4*n);
    set_c.resize(4*n);

    for(int i = 0; i < q; i++) {
        if(v[i] > 0) {
            int x = query_plus(1, 0, n-1, v[i]);
            update(1, 0, n-1, 0, x, 0, 1, 0);
            //cout << x << "\n";
            update(1, 0, n-1, x+1, n-1, 0, 0, v[i]);
        }
        else {
            int x = query_minus(1, 0, n-1, -v[i]);
            update(1, 0, n-1, 0, x, 1, 0, 0);
            update(1, 0, n-1, x+1, n-1, 0, 0, v[i]);
        }
        
        //for(int i = 0; i < n; i++) cout << query(1, 0, n-1, i) << " \n"[i==n-1];
    } 

    vector<int> ans(n);

    for(int i = 0; i < n; i++) ans[s_c[i].sc] = query(1, 0, n-1, i);

    return ans;
}

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