oj.uz

답안 #806844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806844 2023-08-04T10:28:26 Z sentheta 사탕 분배 (IOI21_candies) C++17
100 / 100
 953 ms 35260 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define DBG 0
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

const Int INF = 1e9+5;
const int N = 2e5+5;

int n, q;
V<int> c;
V<int> ql, qr, qv;


#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
// st.qry(t) = height at time t
struct St{
	Int mx[2*N], mn[2*N], lz[2*N];
	void upd(int l,int r,Int x,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			mx[v] += x; mn[v] += x; lz[v] += x;
			return;
		}
		upd(l,r,x, lc,tl,mid);
		upd(l,r,x, rc,mid+1,tr);
		mx[v] = lz[v] + max(mx[lc], mx[rc]);
		mn[v] = lz[v] + min(mn[lc], mn[rc]);
	}
	Int qryMax(int l,int r=q,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return -INF*INF;
		if(l<=tl && tr<=r) return mx[v];
		return lz[v] + max({
			qryMax(l,r, lc,tl,mid), qryMax(l,r, rc,mid+1,tr)
		});
	}
	Int qryMin(int l,int r=q,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return INF*INF;
		if(l<=tl && tr<=r) return mn[v];
		return lz[v] + min({
			qryMin(l,r, lc,tl,mid), qryMin(l,r, rc,mid+1,tr)
		});
	}
} st;

// events
V<int> ev[N];

V<int> distribute_candies(V<int> _c,V<int> _ql,V<int> _qr,V<int> _qv){
	c.swap(_c); ql.swap(_ql); qr.swap(_qr); qv.swap(_qv);
	n = c.size();
	
	// dummy updates
	reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
	ql.push_back(0); qr.push_back(n-1); qv.push_back(-INF);
	ql.push_back(0); qr.push_back(n-1); qv.push_back(+INF);
	reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
	
	q = ql.size();
	
	dbg(q);
	rep(i,0,q){
		cerr << ql[i] _ qr[i] _ qv[i] << nl;
		ev[ql[i]].push_back(i);
		ev[qr[i]+1].push_back(i);
	}
	cerr << nl;
	
	V<int> vans(n);
	rep(i,0,n){
		for(int e : ev[i]){
			// enable
			if(ql[e]==i){
				st.upd(e,q, qv[e]);
			}
			// disable
			else{
				st.upd(e,q, -qv[e]);
			}
			// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
			// cerr << nl << nl;
		}
		
		// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
		// cerr << nl << nl;
		
		// find last wall touch
		int t = 0;
		for(int J=1<<20; J; J/=2)
			if(t+J<q && st.qryMax(t+J)-st.qryMin(t+J)>=c[i]) t+=J;
		t++;
		
		dbg(t);
		dbg(st.qryMax(t));
		dbg(st.qryMin(t));
		dbg(st.qryMax(t)-st.qryMin(t));
		dbg(st.qryMax(t+1));
		dbg(st.qryMin(t+1));
		
		// 
		Int ans;
		Int h = st.qryMax(q), base;
		if(qv[t] > 0){
			base = st.qryMax(t) - c[i];
		}
		else{
			base = st.qryMin(t);
		}
		ans = h - base;
		vans[i] = ans;
		
		dbg(h);
		dbg(base);
		cerr << nl << nl;
		// if(i==1) return vans;
	}
	
	return vans;
	
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 6 ms 5280 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 742 ms 33032 KB Output is correct
2 Correct 953 ms 32008 KB Output is correct
3 Correct 870 ms 31856 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 166 ms 24340 KB Output is correct
3 Correct 265 ms 11764 KB Output is correct
4 Correct 812 ms 34920 KB Output is correct
5 Correct 842 ms 35260 KB Output is correct
6 Correct 661 ms 35152 KB Output is correct
7 Correct 659 ms 33460 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 79 ms 24580 KB Output is correct
4 Correct 196 ms 9668 KB Output is correct
5 Correct 576 ms 27892 KB Output is correct
6 Correct 510 ms 28684 KB Output is correct
7 Correct 352 ms 29532 KB Output is correct
8 Correct 569 ms 27780 KB Output is correct
9 Correct 635 ms 30620 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 6 ms 5280 KB Output is correct
6 Correct 742 ms 33032 KB Output is correct
7 Correct 953 ms 32008 KB Output is correct
8 Correct 870 ms 31856 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 166 ms 24340 KB Output is correct
11 Correct 265 ms 11764 KB Output is correct
12 Correct 812 ms 34920 KB Output is correct
13 Correct 842 ms 35260 KB Output is correct
14 Correct 661 ms 35152 KB Output is correct
15 Correct 659 ms 33460 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 79 ms 24580 KB Output is correct
19 Correct 196 ms 9668 KB Output is correct
20 Correct 576 ms 27892 KB Output is correct
21 Correct 510 ms 28684 KB Output is correct
22 Correct 352 ms 29532 KB Output is correct
23 Correct 569 ms 27780 KB Output is correct
24 Correct 635 ms 30620 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 216 ms 9616 KB Output is correct
27 Correct 163 ms 23956 KB Output is correct
28 Correct 849 ms 32364 KB Output is correct
29 Correct 735 ms 33008 KB Output is correct
30 Correct 739 ms 32940 KB Output is correct
31 Correct 710 ms 33268 KB Output is correct
32 Correct 672 ms 33588 KB Output is correct