Submission #1050420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050420		Alihan_8	Distributing Candies (IOI21_candies)	C++17	100 / 100	189 ms	44632 KiB

candies

#include "candies.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define pb push_back
#define ln '\n'

using i64 = long long;

const int N = 2e5 + 5;

int C;

struct SegTree{
	struct Info{
		i64 mn, mx, s;
		
		Info(i64 k) : mn(min(0LL, k)), mx(max(0LL, k)), s(k) {}
		
		Info() : mn(0), mx(0), s(0) {}
		
		Info(const Info &a, const Info &b){
			s = a.s + b.s;
			mn = min(a.mn, a.s + b.mn);
			mx = max(a.mx, a.s + b.mx);
		}
		
		i64 eval(){
			if ( mx - mn <= C || mn < -C ){
				return s - mn;
			}
			
			return C + s - mx;
		}
	};
	
	vector <Info> T;
	
	int n;
	
	SegTree(int n) : n(n) {
		T.resize(n * 4 + 5);
	}
	
	void upd(int v, int l, int r, int p, i64 x){
		if ( l == r ){
			T[v] = Info(T[v].s + x);
		
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( p <= m ) upd(v * 2, l, m, p, x);
		else  upd(v * 2 + 1, m + 1, r, p, x);
		
		T[v] = Info(T[v * 2], T[v * 2 + 1]);
	}
	
	void upd(int p, i64 x){ upd(1, 0, n, p, x); }
	
	i64 qry(int v, int l, int r, Info p){
		if ( l == r ){
			return Info(T[v], p).eval();
		}
		
		int m = (l + r) / 2;
		
		Info nxt = Info(T[v * 2 + 1], p);
		
		if ( nxt.mx - nxt.mn <= C ){
			return qry(v * 2, l, m, nxt);
		}
		
		return qry(v * 2 + 1, m + 1, r, p);
	} 
	
	i64 qry(int c){ C = c;
		return qry(1, 0, n, Info());
	}
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    
    int q = l.size(), n = c.size();
    
    vector <vector<ar<int,2>>> inc(n + 1);
    
    for ( int i = 0; i < q; i++ ){
		inc[l[i]].pb({i, v[i]});
		inc[r[i] + 1].pb({i, -v[i]});
	}
	
	SegTree seg(q);
	
	vector <int> ans(n);
	
	for ( int i = 0; i < n; i++ ){
		for ( auto &[j, v]: inc[i] ){	
			seg.upd(j + 1, v);
		}
		
		ans[i] = seg.qry(c[i]);
	}
	
	return ans;
}

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