oj.uz

Submission #438076

# Submission time Handle Problem Language Result Execution time Memory
438076 2021-06-27T13:49:17 Z Stickfish Distributing Candies (IOI21_candies) C++17
35 / 100
 814 ms 20176 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 9180 KB Output is correct
2 Correct 120 ms 9284 KB Output is correct
3 Correct 124 ms 9268 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 322 ms 5500 KB Output is correct
3 Correct 114 ms 15172 KB Output is correct
4 Correct 713 ms 20176 KB Output is correct
5 Correct 814 ms 20040 KB Output is correct
6 Correct 760 ms 20044 KB Output is correct
7 Correct 752 ms 20092 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 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 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -