oj.uz

Submission #1081324

# Submission time Handle Problem Language Result Execution time Memory
1081324 2024-08-29T22:40:32 Z Trent Food Court (JOI21_foodcourt) C++17
13 / 100
 106 ms 31312 KB 
#include <iostream>
#include "bits/stdc++.h"
#define forR(i, x) for(int i=0; i < (x); ++i)
#define REP(i, a, b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(), x.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define asst(x) if(!(x)) exit(1)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int MN = 3e5 + 10;
int len[MN];
struct ev{
	int ti;
	ll to;
};
ll ch[MN];
int c[MN];
bool us[MN];
vector<ev> evs[MN];
struct query{
	int ai, i; ll b;
};
vector<query> qus[MN];
int ans[MN];
struct node {
	ll ps, psm;
	ll nSum;
};
node seg[4 * MN];
node comb(node a, node b) {
	return {a.ps + b.ps, min(a.psm, a.ps + b.psm), a.nSum + b.nSum};
}
void upd(int v, int nl, int nr, int i, ll to) {
	if(nl == i && nr == i) seg[v] = {to, min(0LL, to), to < 0 ? to : 0};
	else {
		int mid = (nl+nr)/2;
		if(i <= mid) upd(2*v, nl, mid, i, to);
		else upd(2*v+1, mid+1, nr, i, to);
		seg[v] = comb(seg[2*v], seg[2*v+1]);
	}
}
node qu(int v, int nl, int nr, int l, int r) {
	if(l > r) return {0, 0, 0};
	if(nl == l && nr == r) return seg[v];
	int mid = (nl+nr)/2;
	return comb(qu(2*v, nl, mid, l, min(mid, r)),
			qu(2*v+1, mid+1, nr, max(mid+1, l), r));
}
ll amtOf(node cur) {
	return cur.ps - cur.psm - cur.nSum;
}
int getInd(int v, int nl, int nr, int ti, ll need) {
	if(nl == nr) return amtOf(seg[v]) >= need ? nl : -1;
	int mid = (nl+nr)/2;
	ll lefAmt = amtOf(seg[2*v]);
	if(ti <= mid || lefAmt >= need) {
		return getInd(2*v, nl, mid, ti, need);
	}
	return getInd(2*v+1, mid+1, nr, ti, need - lefAmt);
}

int main(){
	boost();
	int n, m, q; cin >> n >> m >> q;
	int ai=0;
	forR(i, q){
		int ty; cin >> ty;
		if(ty == 1){
			int l, r, k; cin >> l >> r >> c[i] >> k;
			evs[l].push_back({i, k});
			evs[r+1].push_back({i, 0});
		} else if(ty == 2){
			int l, r, k; cin >> l >> r >> k;
			evs[l].push_back({i, -k});
			evs[r+1].push_back({i, 0});
		} else {
			int a; ll b; cin >> a >> b;
			qus[a].push_back({ai++, i, b});
		}
	}
	REP(i, 1, n+1){
		for(auto [ti, to] : evs[i]) {
			ch[ti] = to;
			upd(1, 0, q-1, ti, to);
		}
		for(auto [ai, ti, b] : qus[i]) {
			node ati = qu(1, 0, q-1, ti+1, q-1);
			node tot = qu(1, 0, q-1, 0, q-1);

			ll need = b - tot.nSum + ati.nSum;
			int ind = getInd(1, 0, q-1, ti, need);
			if(ind != -1) {
				node thing = qu(1, 0, q-1, 0, ind);
				asst(thing.ps - thing.psm - thing.nSum >= need);
				ans[ai] = c[ind];
			} else ans[ai] = 0;
		}
	}
	forR(i, ai) cout << ans[i] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14684 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14684 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 21592 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 31312 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14684 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 22296 KB Output is correct
2 Correct 57 ms 22652 KB Output is correct
3 Correct 57 ms 22868 KB Output is correct
4 Correct 46 ms 21340 KB Output is correct
5 Correct 55 ms 22096 KB Output is correct
6 Correct 57 ms 22868 KB Output is correct
7 Correct 36 ms 21176 KB Output is correct
8 Correct 35 ms 20776 KB Output is correct
9 Correct 46 ms 21960 KB Output is correct
10 Correct 41 ms 21080 KB Output is correct
11 Correct 59 ms 22612 KB Output is correct
12 Correct 52 ms 22612 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14684 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14684 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -