oj.uz

Submission #438079

# Submission time Handle Problem Language Result Execution time Memory
438079 2021-06-27T13:50:37 Z Stickfish Distributing Candies (IOI21_candies) C++17
38 / 100
 809 ms 19768 KB 
#include "candies.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;
const ll INF = 1e18 + 177013;

struct upd{
	ll add;
	pair<ll, ll> sg;

	upd(): add(0), sg(0, INF) {}

	upd(ll add_, ll mineq_, ll maxeq_): add(add_), sg(maxeq_, mineq_){}
};

ll into_seg(ll x, pair<ll, ll> sg){
	if(x < sg.first)
		return sg.first;
	if(x > sg.second)
		return sg.second;
	return x;
}

pair<ll, ll> cover(pair<ll, ll> oldsg, pair<ll, ll> newsg){
	return {into_seg(oldsg.first, newsg), into_seg(oldsg.second, newsg)};
}

struct stree{
	void init(int n){
		sz = 1;
		while(sz < n)
			sz *= 2;
		mod.assign(sz * 2 - 1, upd());
	}

	void add(int l, int r, ll vl){
		add(0, 0, sz, l, r, vl);
	}

	void mineq(int l, int r, ll vl){
		mineq(0, 0, sz, l, r, vl);
	}

	void maxeq(int l, int r, ll vl){
		maxeq(0, 0, sz, l, r, vl);
	}

	ll get(int i){
		return get(0, 0, sz, i);
	}
private:
	int sz;
	vector<upd> mod;

	void push(int ind){
		if(ind * 2 + 1 >= sz * 2 - 1)
			return;
		mod[ind * 2 + 1].add += mod[ind].add;
		mod[ind * 2 + 1].sg.first += mod[ind].add;
		mod[ind * 2 + 1].sg.second += mod[ind].add;
		mod[ind * 2 + 1].sg = cover(mod[ind * 2 + 1].sg, mod[ind].sg);
		
		mod[ind * 2 + 2].add += mod[ind].add;
		mod[ind * 2 + 2].sg.first += mod[ind].add;
		mod[ind * 2 + 2].sg.second += mod[ind].add;
		mod[ind * 2 + 2].sg = cover(mod[ind * 2 + 2].sg, mod[ind].sg);

		mod[ind] = upd();
	}

	void add(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].add += vl;
			mod[ind].sg.first += vl;
			mod[ind].sg.second += vl;
			return;
		}
		int mnd = (lnd + rnd) / 2;
		add(ind * 2 + 1, lnd, mnd, l, r, vl);
		add(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	void mineq(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].sg = cover(mod[ind].sg, {-INF, vl});
			return;
		}
		int mnd = (lnd + rnd) / 2;
		mineq(ind * 2 + 1, lnd, mnd, l, r, vl);
		mineq(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	void maxeq(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].sg = cover(mod[ind].sg, {vl, INF});
			return;
		}
		int mnd = (lnd + rnd) / 2;
		maxeq(ind * 2 + 1, lnd, mnd, l, r, vl);
		maxeq(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	ll get(int ind, int lnd, int rnd, int i){
		push(ind);
		if(rnd - lnd == 1){
			return into_seg(mod[ind].add, mod[ind].sg);
		}
		int mnd = (lnd + rnd) / 2;
		if(i < mnd)
			return get(ind * 2 + 1, lnd, mnd, i);
		return get(ind * 2 + 2, mnd, rnd, i);
	}
};


vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
	int q = l.size();
    vector<int> s(n, 0);
	for(int i = 0; i < q; ++i)
		++r[i];

	if(n <= 2000){
		for(int qi = 0; qi < q; ++qi){
			for(int i = l[qi]; i < r[qi]; ++i){
				s[i] += v[qi];
				s[i] = max(s[i], 0);
				s[i] = min(s[i], c[i]);
			}
		}
		return s;
	}

	bool isv_positive = true;
	for(int i = 0; i < q; ++i)
		isv_positive &= v[i] >= 0;
	if(isv_positive){
		vector<ll> pf(n + 1, 0);
		for(int qi = 0; qi < q; ++qi){
			pf[l[qi]] += v[qi];
			pf[r[qi]] -= v[qi];
		}
		ll sm = 0;
		for(int i = 0; i < n; ++i){
			sm += pf[i];
			s[i] = int(min(sm, 1ll * c[i]));
		}
		return s;
	} else {
		stree tr;
		tr.init(n);
		for(int i = 0; i < q; ++i){
			tr.add(l[i], r[i], v[i]);
			//cout << "--- add " << l[i] << ' ' << r[i] << ' ' << v[i] << " ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
			tr.mineq(0, n, c[0]);
			//cout << "--- mineq ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
			tr.maxeq(0, n, 0);
			//cout << "--- maxeq ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
		}
		for(int i = 0; i < n; ++i){
			s[i] = tr.get(i);
		}
	}
    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8792 KB Output is correct
2 Correct 128 ms 8880 KB Output is correct
3 Correct 127 ms 8872 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 251 ms 5080 KB Output is correct
3 Correct 112 ms 14884 KB Output is correct
4 Correct 722 ms 19660 KB Output is correct
5 Correct 742 ms 19656 KB Output is correct
6 Correct 738 ms 19768 KB Output is correct
7 Correct 809 ms 19760 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 597 ms 5444 KB Output is correct
4 Incorrect 102 ms 15164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 134 ms 8792 KB Output is correct
7 Correct 128 ms 8880 KB Output is correct
8 Correct 127 ms 8872 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 251 ms 5080 KB Output is correct
11 Correct 112 ms 14884 KB Output is correct
12 Correct 722 ms 19660 KB Output is correct
13 Correct 742 ms 19656 KB Output is correct
14 Correct 738 ms 19768 KB Output is correct
15 Correct 809 ms 19760 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 597 ms 5444 KB Output is correct
19 Incorrect 102 ms 15164 KB Output isn't correct
20 Halted 0 ms 0 KB -