oj.uz

Submission #972052

# Submission time Handle Problem Language Result Execution time Memory
972052 2024-04-30T01:24:20 Z penguin133 Distributing Candies (IOI21_candies) C++17
8 / 100
 491 ms 61632 KB 
#include <bits/stdc++.h>
using namespace std;
#include "candies.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct dat{
	ll sm, mx, mn, mxpre, mnpre, mxsuf, mnsuf;
};

dat comb(dat a, dat b){
	dat ans;
	ans.sm = a.sm + b.sm;
	ans.mx = max({a.mx, b.mx, a.mxsuf + b.mxpre});
	ans.mn = min({a.mn, b.mn, a.mnsuf + b.mnpre});
	ans.mxpre = max(a.mxpre, a.sm + b.mxpre);
	ans.mnpre = min(a.mnpre, a.sm + b.mnpre);
	ans.mxsuf = max(b.mxsuf, b.sm + a.mxsuf);
	ans.mnsuf = min(b.mnsuf, b.sm + a.mnsuf);
	return ans;
}

struct node{
	int s, e, m;
	dat val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m + 1, e);
		val.sm = val.mx = val.mn = val.mxpre = val.mnpre = val.mxsuf = val.mnsuf = 0;
	}
	
	void upd(int p, int v){
		if(s == e){
			val.sm = val.mx = val.mn = val.mxpre = val.mnpre = val.mxsuf = val.mnsuf = v;
		}
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = comb(l->val, r->val);
		}
	}
	
	ll fd(ll cap){
		if(s == e)return (val.sm > cap ? cap : (val.sm < 0 ? 0 : val.sm));
		if(r->val.mx > cap || r->val.mn < -cap)return r->fd(cap);
		else if(l->val.mxsuf + r->val.mxpre > cap)return r->val.sm - r->val.mxpre + cap;
		else if(l->val.mnsuf + r->val.mnpre < -cap)return r->val.sm - r->val.mnpre;
		else return l->fd(cap) + r->val.sm;
	}
}*root;

vector <pi> Q[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size(), q = (int)l.size();
    for(int i = 0; i < q; i++){
		Q[l[i]].push_back({i, v[i]});
		Q[r[i] + 1].push_back({i, 0});
	}
	root = new node(0, q - 1);
	vector <int> ans(n);
	for(int i = 0; i < n; i++){
		for(auto [a, b] : Q[i]){
			root->upd(a, b);
		}
		ans[i] = root->fd(c[i]);
	}
	return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 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 491 ms 61632 KB Output is correct
2 Correct 460 ms 60868 KB Output is correct
3 Correct 447 ms 60700 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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