oj.uz

답안 #806846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806846 2023-08-04T10:29:18 Z sentheta 사탕 분배 (IOI21_candies) C++17
100 / 100
 950 ms 29044 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 3 ms 5000 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 6 ms 5272 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 763 ms 28196 KB Output is correct
2 Correct 798 ms 27928 KB Output is correct
3 Correct 950 ms 27940 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 181 ms 21384 KB Output is correct
3 Correct 222 ms 9508 KB Output is correct
4 Correct 826 ms 28956 KB Output is correct
5 Correct 815 ms 29044 KB Output is correct
6 Correct 709 ms 28448 KB Output is correct
7 Correct 686 ms 27412 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 80 ms 21980 KB Output is correct
4 Correct 206 ms 8464 KB Output is correct
5 Correct 532 ms 24476 KB Output is correct
6 Correct 543 ms 24508 KB Output is correct
7 Correct 348 ms 24720 KB Output is correct
8 Correct 550 ms 24412 KB Output is correct
9 Correct 674 ms 25788 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 6 ms 5272 KB Output is correct
6 Correct 763 ms 28196 KB Output is correct
7 Correct 798 ms 27928 KB Output is correct
8 Correct 950 ms 27940 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 181 ms 21384 KB Output is correct
11 Correct 222 ms 9508 KB Output is correct
12 Correct 826 ms 28956 KB Output is correct
13 Correct 815 ms 29044 KB Output is correct
14 Correct 709 ms 28448 KB Output is correct
15 Correct 686 ms 27412 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 80 ms 21980 KB Output is correct
19 Correct 206 ms 8464 KB Output is correct
20 Correct 532 ms 24476 KB Output is correct
21 Correct 543 ms 24508 KB Output is correct
22 Correct 348 ms 24720 KB Output is correct
23 Correct 550 ms 24412 KB Output is correct
24 Correct 674 ms 25788 KB Output is correct
25 Correct 2 ms 4948 KB Output is correct
26 Correct 215 ms 8432 KB Output is correct
27 Correct 176 ms 21408 KB Output is correct
28 Correct 827 ms 27932 KB Output is correct
29 Correct 701 ms 28064 KB Output is correct
30 Correct 675 ms 27804 KB Output is correct
31 Correct 748 ms 27884 KB Output is correct
32 Correct 570 ms 28060 KB Output is correct