oj.uz

Submission #521518

# Submission time Handle Problem Language Result Execution time Memory
521518 2022-02-02T10:15:50 Z amunduzbaev Food Court (JOI21_foodcourt) C++14
13 / 100
 802 ms 62016 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 25e4 + 5;

struct node{
	int t, l, r, c, k, a, b;
};
struct BIT{
	int tree[N<<2], p[2][N<<2];
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1] += p[0][x], tree[x<<1|1] += p[0][x];
		p[0][x<<1] += p[0][x], p[0][x<<1|1] += p[0][x];
		p[1][x<<1] += p[0][x], p[1][x<<1|1] += p[0][x];
		
		tree[x<<1] = max(tree[x<<1], p[1][x]);
		p[1][x<<1] = max(p[1][x<<1], p[1][x]);
		p[0][x<<1] = max(p[0][x<<1], p[1][x]);
		tree[x<<1|1] = max(tree[x<<1|1], p[1][x]);
		p[1][x<<1|1] = max(p[1][x<<1|1], p[1][x]);
		p[0][x<<1|1] = max(p[0][x<<1|1], p[1][x]);
		p[0][x] = 0, p[1][x] = -1e18;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		push(x, lx, rx);
		if(lx >= l && rx <= r){
			tree[x] += v;
			p[0][x] += v, p[1][x] += v;
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x<<1), 
		add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		push(x, lx, rx);
		if(lx >= l && rx <= r){
			tree[x] = max(tree[x], v);
			p[1][x] = max(p[1][x], v);
			p[0][x] = max(p[0][x], v);
			return;
		} int m = (lx + rx) >> 1;
		umax(l, r, v, lx, m, x<<1), 
		umax(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, lx, m, x<<1);
		else return get(i, m+1, rx, x<<1|1);
	}
}cur, tot;

struct ST2{
	ar<int, 2> tree[N<<2];
	int p[N<<2];
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1][0] += p[x], tree[x<<1|1][0] += p[x];
		p[x<<1] += p[x], p[x<<1|1] += p[x];
		p[x] = 0;
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = {v, i}; return; }
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			p[x] += v; return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x<<1), 
		add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {(int)1e18, (int)1e18};
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

int res[N], pos[N];
vector<int> qq[N];
node a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	memset(cur.p[1], 128, sizeof cur.p[1]);
	
	int n, m, q; cin>>n>>m>>q;
	for(int i=0;i<q;i++){
		cin>>a[i].t;
		if(a[i].t == 1){
			cin>>a[i].l>>a[i].r>>a[i].c>>a[i].k;
			cur.add(a[i].l, a[i].r, a[i].k);
			tot.add(a[i].l, a[i].r, a[i].k);
		} if(a[i].t == 2){
			cin>>a[i].l>>a[i].r>>a[i].k;
			cur.add(a[i].l, a[i].r, -a[i].k);
			cur.umax(a[i].l, a[i].r, 0);
		} if(a[i].t == 3){
			cin>>a[i].a>>a[i].b;
			int c = cur.get(a[i].a), t = tot.get(a[i].a) - c;
			if(a[i].b > c) res[i] = 0;
			else {
				qq[a[i].a].push_back(i);
				pos[i] = t + a[i].b;
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
			return (pos[i] > pos[j]);
		});
		
		if(qq[i].empty()) tree.sett(i, 1e18);
		else tree.sett(i, pos[qq[i].back()]);
	}
	
	for(auto x : a){
		if(x.t != 1) continue;
		tree.add(x.l, x.r, -x.k);
		auto mn = tree.get(x.l, x.r);
		while(mn[0] <= 0){
			int i = mn[1], last = qq[i].back();
			qq[i].pop_back();
			res[last] = x.c;
			if(qq[i].empty()) tree.sett(i, 1e18);
			else tree.sett(i, pos[qq[i].back()] - pos[last] + mn[0]);
			mn = tree.get(x.l, x.r);
		}
	}
	
	for(int i=0;i<q;i++){
		if(a[i].t == 3) cout<<res[i]<<"\n";
	} cout<<"\n";
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 14668 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 181 ms 27360 KB Output is correct
2 Correct 168 ms 28356 KB Output is correct
3 Correct 211 ms 29828 KB Output is correct
4 Correct 171 ms 27296 KB Output is correct
5 Correct 161 ms 28552 KB Output is correct
6 Correct 200 ms 29896 KB Output is correct
7 Correct 90 ms 20048 KB Output is correct
8 Correct 77 ms 19656 KB Output is correct
9 Correct 180 ms 29768 KB Output is correct
10 Correct 122 ms 26688 KB Output is correct
11 Correct 171 ms 29812 KB Output is correct
12 Correct 175 ms 29808 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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