제출 #1363090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363090		Jawad_Akbar_JJ	푸드 코트 (JOI21_foodcourt)	C++20	100 / 100	212 ms	46208 KiB

foodcourt

#include <iostream>
#include <vector>

using namespace std;
#define int long long
const int N = 1<<18;
int Sum[N<<1], Lz[N<<1], Mn[N<<1], tp[N], Ans[N], n, m, q;
vector<pair<int, int>> v1[N], v2[N], Q[N];

void Push(int cur, int lc, int rc){
	Lz[lc] += Lz[cur], Mn[lc] += Lz[cur];
	Lz[rc] += Lz[cur], Mn[rc] += Lz[cur];
	Lz[cur] = 0;
}

void Add(int l, int r, int v, int cur = 1, int st = 0, int en = N){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		Lz[cur] += v;
		Mn[cur] += v;
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);

	Add(l, r, v, lc, st, mid);
	Add(l, r, v, rc, mid, en);

	Mn[cur] = min(Mn[lc], Mn[rc]);
}
int getMin(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mn[cur];

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);

	return min(getMin(l, r, lc, st, mid), getMin(l, r, rc, mid, en));
}

int get0(int i){
	int ans = -getMin(0, i);
	for (i += N; i; i /= 2)
		ans += Lz[i];
	return ans;
}

void Add(int i, int v){
	for (i += N; i; i /= 2)
		Sum[i] += v;
}

int get1(int i, int B){
	for (i += N + 1; i; i /= 2){
		if (!(i & 1))
			continue;
		if (i != 1 and Sum[i ^ 1] < B){
			B -= Sum[i ^ 1];
			continue;
		}
		i -= i > 1;
		while (i < N){
			i += i + 1;
			if (Sum[i] < B)
				B -= Sum[i], i--;
		}
		return i - N;
	}
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m>>q;

	for (int i=1, t, l, r, c;i<=q;i++){
		cin>>t>>l>>r;
		if (t == 1){
			cin>>tp[i]>>c;
			v1[l].push_back({i, c});
			v1[r+1].push_back({i, -c});
		}
		else if (t == 2){
			cin>>c;
			v2[l].push_back({i, -c});
			v2[r+1].push_back({i, c});
		}
		else{
			Q[l].push_back({i, r});
		}
	}

	for (int i=1;i<=n;i++){
		for (auto [t, v] : v1[i])
			Add(t, N, v), Add(t, v);

		for (auto [t, v] : v2[i])
			Add(t, N, v);

		for (auto [t, B] : Q[i]){
			int X = get0(t);
			if (X >= B)
				Ans[t] = tp[get1(t, X - B + 1)];
			Ans[t]++;
		}
	}

	for (int i=1;i<=q;i++){
		if (Ans[i])
			cout<<Ans[i] - 1<<'\n';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'long long int get1(long long int, long long int)':
foodcourt.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

• 서브태스크 1: 2 / 2
• 서브태스크 2: 5 / 5
• 서브태스크 3: 7 / 7
• 서브태스크 4: 21 / 21
• 서브태스크 5: 15 / 15
• 서브태스크 6: 13 / 13
• 서브태스크 7: 26 / 26
• 서브태스크 8: 11 / 11