Submission #1216866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216866		thelegendary08	Distributing Candies (IOI21_candies)	C++17	0 / 100	304 ms	46652 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<long long>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
int cap;
struct segtree{
	int n; vi mn, mx; vi tl; vi tr; vi la; vi ls; vi dx;
	segtree(int x){
		n = x; int mxn = 4 * n + 5;
		mn.resize(mxn); mx.resize(mxn); tl.resize(mxn); tr.resize(mxn); la.resize(mxn); ls.resize(mxn); dx.resize(n); build(1, 0, n-1);
	}
	void pull(int v){
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
	void build(int v, int l, int r){
		tl[v] = l; tr[v] = r;
		if(l == r){
			return;
		}
		int mid = (l + r) / 2;
		build(v * 2, l, mid);
		build(v * 2 + 1, mid + 1, r);
		pull(v);
	}
	int sz(int v){
		return tr[v] - tl[v] + 1;
	}
	void add(int v, int x){
		la[v] += x;
		mn[v] += x;
		mx[v] += x;
	}
	void sett(int v, int x){
		ls[v] = x; la[v] = 0;
		mn[v] = x; mx[v] = x;
	}
	void push(int v){
		if(ls[v]){
			sett(v*2,ls[v]);
			sett(v*2+1,ls[v]);
			ls[v] = 0;
		}
		if(la[v]){
			add(v*2, la[v]);
			add(v * 2 +1, la[v]);
			la[v] = 0;
		}
	}
	
	void upd(int v, int l, int r, int x){
		// cout<<tl[v]<<' '<<tr[v]<<' '<<x<<'\n';
		if(tl[v] > r || tr[v] < l)return;
		if(tl[v] >= l && tr[v] <= r){
			if(x > 0){
				if(mx[v] + x <= cap){
					// cout<<tl[v]<<' '<<tr[v]<<' '<<x<<'\n';
					add(v, x); return;
				}
				if(mn[v] + x >= cap){
					sett(v, cap); return; 
				}
			}
			else{
				if(mn[v] + x >= 0){
					add(v, x); return;
				}
				if(mx[v] + x <= 0){
					sett(v, 0); return;
				}
			}
		}
		push(v);
		upd(v * 2, l, r, x);
		upd(v * 2 + 1, l, r, x);
		pull(v);
	}
	int quer(int v, int x){
		if(tl[v] > x || tr[v] < x)return 0;
		if(tl[v] == x && tr[v] == x)return mn[v];
		push(v);
		int ret = quer(v * 2, x) + quer(v * 2 + 1, x);
		pull(v);
		return ret;
	}
	
};
std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
    int n = c.size(); cap = c[0];
    vector<signed> ans(n);
    int q = l.size();
    segtree s = segtree(n);
    f0r(i, q){
    	s.upd(1, l[i], r[i], v[i]);
    }
    f0r(i,n){
    	ans[i] = s.quer(1, i);
    }
    return ans;
}

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