oj.uz

Submission #1041172

# Submission time Handle Problem Language Result Execution time Memory
1041172 2024-08-01T16:41:40 Z Alihan_8 Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 43860 KB 
#include "candies.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e16;

const int N = 2e5 + 5;

//~ {
	//~ if ( l > tr or r < tl ){
		//~ return inf;
	//~ }
	
	//~ if ( l <= tl && tr >= r ){
		//~ if ( T[v].mx <= bound ){
			//~ return T[v].mn;
		//~ }
		
		//~ if ( l == r ) return inf;
			
		//~ int m = (l + r) / 2;
		
		//~ int ret = get(v * 2 + 1, m + 1, r, tl, tr);
		
		//~ if ( T[v * 2 + 1].mx <= bound ){
			//~ chmin(ret, get(v * 2, l, m, tl, tr));
		//~ } 
		
		//~ return ret;
	//~ }
//~ }

struct SegTree{
	vector <ar<i64,2>> T;
	
	vector <i64> lazy;
	
	int n;
	
	SegTree(int n) : n(n) {
		T.resize(N * 4);
		lazy.resize(N * 4);
		
		for ( int i = 0; i < N * 4; i++ ){
			T[i] = {inf, inf};
			
			lazy[i] = 0;
		}
	}
	
	void push(int v, int l, int r){
		if ( l != r ){
			lazy[v * 2] += lazy[v];
			lazy[v * 2 + 1] += lazy[v];
		}
		
		T[v][0] += lazy[v];
		T[v][1] -= lazy[v];
		lazy[v] = 0;
	}
	
	void upd(int v, int l, int r, int tl, int tr, i64 x){
		push(v, l, r);
		
		if ( l > tr or r < tl ) return;
		
		if ( tl <= l && tr >= r ){
			lazy[v] += x;
			
			push(v, l, r);
			
			return;
		}
		
		int m = (l + r) / 2;
		
		upd(v * 2, l, m, tl, tr, x);
		upd(v * 2 + 1, m + 1, r, tl, tr, x);
		
		for ( auto j: {0, 1} ){
			T[v][j] = min(T[v * 2][j], T[v * 2 + 1][j]);
		}
	}
	
	void upd(int l, int r, i64 x){
		upd(1, 0, n, l, r, x);
	}
	
	void set(int v, int l, int r, int ps, i64 x){
		push(v, l, r);
		
		if ( l == r ){
			T[v] = {x, -x};
			
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( ps <= m ) set(v * 2, l, m, ps, x);
		else set(v * 2 + 1, m + 1, r, ps, x);
		
		for ( auto j: {0, 1} ){
			T[v][j] = min(T[v * 2][j], T[v * 2 + 1][j]);
		}
	}
	
	void set(int ps, i64 x){
		set(1, 0, n, ps, x);
	}
	
	i64 get(int v, int l, int r, int tl, int tr, int j){
		push(v, l, r);
		
		if ( l > tr or r < tl ) return inf;
		
		if ( tl <= l && tr >= r ){
			return T[v][j];
		}
		
		int m = (l + r) / 2;
		
		return min(get(v * 2, l, m, tl, tr, j), get(v * 2 + 1, m + 1, r, tl, tr, j));
	}
	
	i64 get(int l, int r, int j){ // 0 - min, 1 - max
		return get(1, 0, n, l, r, j) * (!j ? 1 : -1);
	}
	
	bool in(i64 l, i64 r, i64 u){ return l <= u && r >= u; } 
	
	i64 f(int v, int l, int r, int tl, int tr, i64 L, i64 R, int j){ 
		push(v, l, r);
		
		if ( l > tr or r < tl ) return inf;
		
		int m = (l + r) / 2;
		
		if ( tl <= l && tr >= r ){
			if ( !in(L, R, -T[v][1]) || !in(L, R, T[v][0]) ){
				return inf;
			}
			
			i64 ret = f(v * 2 + 1, m + 1, r, tl, tr, L, R, j);
			
			if ( in(L, R, -T[v * 2 + 1][1]) && in(L, R, T[v * 2 + 1][0]) ){
				chmin(ret, f(v * 2, l, m, tl, tr, L, R, j));
			}
			
			return ret;
		}
		
		//~ not finished
	}
};

struct Fenwick{
	vector <i64> fn;
	
	int n;
	
	Fenwick(int n) : fn(n + 1, 0), n(n) {}
	
	void upd(int i, int x){
		for (; i <= n; i += i & -i ){
			fn[i] += x;
		}
	}
	
	i64 get(int i){
		i64 ret = 0;
		
		for (; i > 0; i -= i & -i ){
			ret += fn[i];
		}
		
		return ret;
	}
	
	i64 get(int l, int r){
		return get(r) - get(l - 1);
	}
};

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<int>> H(n + 1);
    
    for ( int i = 0; i < q; i++ ){
		H[l[i]].pb(i + 1);
		H[r[i] + 1].pb(-(i + 1));
	}
	
	vector <int> ans(n);
	
	SegTree seg(q);
	
	for ( int j = 0; j <= q; j++ ){
		seg.set(j, 0);
	}
	
	i64 pf = 0, mn = 0;
	
	for ( int j = 0; j < q; j++ ){
		pf += v[j];
		
		chmin(mn, pf);
	}
	
	Fenwick fn(q + 1);
	
	for ( int i = 0; i < n; i++ ){
		for ( auto &j: H[i] ){
			int u = abs(j);
			
			i64 x = j < 0 ? -v[u - 1] : v[u - 1];
			
			seg.upd(u, q, x);
			fn.upd(u, x);
		}
		
		auto ok = [&](int m){
			i64 mn = seg.get(m, q, 0), mx = seg.get(m, q, 1);
			
			//~ cout << "Min on Seg " << m << " " << q << " -> " << mn << ", " << mx << ln;
			
			if ( mx - mn >= c[i] ){
				return true;
			}
			
			{ // mx case
				int l = 0, r = m;
				
				while ( l < r ){
					int x = (l + r) / 2;
					
					if ( seg.get(x, m, 1) > mx ){
						l = x + 1;
					} else r = x;
				}
				
				if ( mx - seg.get(l, m, 0) >= c[i] ){
					return true;
				}
			}
			
			{ // mn case
				int l = 0, r = m;
				
				while ( l < r ){
					int x = (l + r) / 2;
					
					if ( seg.get(x, m, 0) < mn ){
						l = x + 1;
					} else r = x;
				}
				
				if ( seg.get(l, m, 1) - mn >= c[i] ){
					return true;
				}
			}
			
			return false;
		};
		
		int l = 0, r = q + 1;
		
		while ( l + 1 < r ){
			int m = (l + r) / 2;
			
			if ( ok(m) ) l = m;
			else r = m;
		}
		
		//~ for ( int j = 1; j <= q; j++ ){
			//~ cout << (fn.get(j, j)) <<  ' ';
		//~ } cout << ln;
		//~ for ( int j = 1; j <= q; j++ ){
			//~ cout << seg.get(j, j, 0) << ' ';
		//~ } cout << ln;
		
		//~ cout << i << " -> " << l << ln;
		
		if ( l == 0 ){ // no touch
			ans[i] = fn.get(r, q) - seg.get(0, q, 0);
		} else{
			ans[i] = fn.get(r, q);
			
			int t = -1;
			
			for ( int j = l; j > 0; j-- ){
				if ( fn.get(j, j) ){
					t = (fn.get(j, j) < 0 ? 0 : 1);
					
					break;
				}
			}
			
			assert(t != -1);
			
			ans[i] += c[i] * t;
		}
	}
	
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 6 ms 19156 KB Output is correct
5 Correct 21 ms 19292 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5028 ms 40792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 324 ms 30388 KB Output is correct
3 Correct 2869 ms 28656 KB Output is correct
4 Execution timed out 5060 ms 43860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 4 ms 19124 KB Output is correct
3 Correct 176 ms 29116 KB Output is correct
4 Correct 1458 ms 27264 KB Output is correct
5 Execution timed out 5080 ms 36540 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 6 ms 19156 KB Output is correct
5 Correct 21 ms 19292 KB Output is correct
6 Execution timed out 5028 ms 40792 KB Time limit exceeded
7 Halted 0 ms 0 KB -