oj.uz

Submission #465381

# Submission time Handle Problem Language Result Execution time Memory
465381 2021-08-15T19:18:25 Z koioi.org-dennisstar Food Court (JOI21_foodcourt) C++17
13 / 100
 558 ms 48932 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 1<<19;

struct nd {
	ll v, mn;
	int i;
	nd() : v(0), mn(0), i(0) {}
}st[MX];

pair<ll, ll> pn[MX];

nd operator +(nd u, nd v) {
	nd r;
	r.v=u.v+v.v;
	if (u.mn<u.v+v.mn) r.mn=u.mn, r.i=u.i;
	else r.mn=u.v+v.mn, r.i=v.i;
	return r;
}

pair<ll, ll> operator +(pair<ll, ll> u, pair<ll, ll> v) {
	return {u.first+v.first, u.second+v.second};
}

void init(int i, int s, int e) {
	if (s==e) { st[i].i=-s; return ; }
	int m=(s+e)/2;
	init(i*2, s, m); init(i*2+1, m+1, e);
}

void upd(int i, int s, int e, int t, int v) {
	if (s==e) {
		st[i].v=v;
		st[i].mn=v;
		pn[i]={max(v, 0), min(v, 0)};
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, v);
	else upd(i*2+1, m+1, e, t, v);
	st[i]=st[i*2]+st[i*2+1];
	pn[i]=pn[i*2]+pn[i*2+1];
}

nd get(int i, int s, int e, int t) {
	if (t<s) return nd();
	if (e<=t) return st[i];
	int m=(s+e)/2;
	return get(i*2, s, m, t)+get(i*2+1, m+1, e, t);
}

pair<ll, ll> get(int i, int s, int e, int l, int r) {
	if (e<l||r<s||r<l) return {0, 0};
	if (l<=s&&e<=r) return pn[i];
	int m=(s+e)/2;
	return get(i*2, s, m, l, r)+get(i*2+1, m+1, e, l, r);
}

int srh(int i, int s, int e, ll v) {
	if (s==e) {
		if (pn[i].first>=v) return s;
		return s+1;
	}
	int m=(s+e)/2;
	if (pn[i*2].first>=v) return srh(i*2, s, m, v);
	else return srh(i*2+1, m+1, e, v-pn[i*2].first);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m, q;
	cin>>n>>m>>q;
	
	vector<int> ty(q+1);
	vector<vector<pair<int, ll>>> ch(n+2), ask(n+1);
	vector<pair<int, int>> ans;
	
	for (int i=1; i<=q; i++) {
		int qu;
		cin>>qu;
		if (qu==1) {
			int l, r, k;
			cin>>l>>r>>ty[i]>>k;
			ch[l].emplace_back(i, k);
			ch[r+1].emplace_back(i, 0);
		}
		if (qu==2) {
			int l, r, k;
			cin>>l>>r>>k;
			ch[l].emplace_back(i, -k);
			ch[r+1].emplace_back(i, 0);
		}
		if (qu==3) {
			int a; ll b;
			cin>>a>>b;
			ask[a].emplace_back(i, b);
		}
	}

	init(1, 0, q);
	for (int i=1; i<=n; i++) {
		for (auto &j:ch[i]) upd(1, 0, q, j.first, j.second);
		for (auto &j:ask[i]) {
			int mi=-get(1, 0, q, j.first).i;
			int ai=srh(1, 0, q, get(1, 0, q, 0, mi).first-get(1, 0, q, mi+1, j.first).second+j.second);
			ans.emplace_back(j.first, ai>j.first?0:ty[ai]);
		}
	}
	
	sort(ans.begin(), ans.end());
	for (auto &i:ans) cout<<i.second<<'\n';

	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 22404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 558 ms 48932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 22080 KB Output is correct
2 Correct 132 ms 22188 KB Output is correct
3 Correct 139 ms 22728 KB Output is correct
4 Correct 88 ms 21156 KB Output is correct
5 Correct 106 ms 21976 KB Output is correct
6 Correct 160 ms 22848 KB Output is correct
7 Correct 64 ms 18016 KB Output is correct
8 Correct 64 ms 17804 KB Output is correct
9 Correct 90 ms 22068 KB Output is correct
10 Correct 82 ms 20864 KB Output is correct
11 Correct 139 ms 22460 KB Output is correct
12 Correct 127 ms 22460 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -