Submission #741074

#	Time	Username	Problem	Language	Result	Execution time	Memory
741074		Dan4Life	Food Court (JOI21_foodcourt)	C++17	0 / 100	378 ms	24300 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
const int mxN = (int)2.5e5+10;
const int LINF = (int)2e18;
int n, m, q, segTree[mxN*2];
pair<int,int> lazy[mxN*2];

void prop(int p, int l, int r){
	if(l==r or lazy[p].se==-1) return;
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	lazy[p+1].fi += lazy[p].fi; lazy[p+1].se = lazy[p].se;
	segTree[p+1] = max(segTree[p+1]+lazy[p+1].fi*(mid-l+1),lazy[p+1].se);
	lazy[rp].fi += lazy[p].fi; lazy[rp].se = lazy[p].se;
	segTree[rp] = max(segTree[rp]+lazy[rp].fi*(r-mid),lazy[rp].se);
	lazy[p] = {0,-1};
}

void upd(int i, int j, int v, int p=0, int l=1, int r=n){
	if(i>r or j<l or i>j) return; prop(p,l,r);
	if(i<=l and r<=j){
		lazy[p].fi+=v; lazy[p].se = (v>=0)*-LINF;
		segTree[p]=max(segTree[p]+v*(r-l+1),lazy[p].se);
		return;
	}
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(i<=mid) upd(i,j,v,p+1,l,mid);
	if(j>mid) upd(i,j,v,rp,mid+1,r);
	segTree[p] = segTree[p+1]+segTree[rp];
}

int query(int i, int p=0, int l=1, int r=n){
	prop(p,l,r);
	if(l==r) return segTree[p];
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(i<=mid) return query(i,p+1,l,mid);
	return query(i,rp,mid+1,r);
}

struct SegTree{
	int segTree[mxN*2], lazy[mxN*2], n;
	void init(int N){
		n = N;
		fill(segTree,segTree+n*2,0ll);
		fill(lazy,lazy+n*2,0ll);
	}

	void prop(int p, int l, int r){
		if(l==r or !lazy[p]) return;
		int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
		lazy[p+1]+=lazy[p]; lazy[rp]+=lazy[p]; lazy[p]=0;
		segTree[p+1]+=lazy[p+1]*(mid-l+1);
		segTree[rp]+=lazy[rp]*(r-mid);
	}

	void upd(int i, int j, int v, int p, int l, int r){
		if(i>r or j<l or i>j) return; prop(p,l,r);
		if(i<=l and r<=j){ segTree[p]+=v*(r-l+1); lazy[p]+=v; return; }
		int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
		if(i<=mid) upd(i,j,v,p+1,l,mid);
		if(j>mid) upd(i,j,v,rp,mid+1,r);
	}

	int query(int i, int p, int l, int r){
		prop(p,l,r);
		if(l==r) return segTree[p];
		int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
		if(i<=mid) return query(i,p+1,l,mid);
		return query(i,rp,mid+1,r);
	}
	void upd(int i, int j, int v){
		upd(i,j,v,0,1,n);
	}
	int query(int i){
		return query(i,0,1,n);
	}
} tot;

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> q; tot.init(n);
	for(int i = 0; i < mxN*2; i++) lazy[i] = {0,-1};
	for(int i = 0; i < q; i++){
		int t, l, r, a, b, c, k; cin >> t;
		if(t==1){
			cin >> l >> r >> c >> k;
			upd(l,r,k); tot.upd(l,r,k);
		}
		else if(t==2){
			cin >> l >> r >> k;
			upd(l,r,-k);
		}
		else{
			cin >> a >> b;
			cout << (b<=query(a)) << "\n";
		}
	}
}

Compilation message (stderr)

foodcourt.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:24:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |  if(i>r or j<l or i>j) return; prop(p,l,r);
      |  ^~
foodcourt.cpp:24:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |  if(i>r or j<l or i>j) return; prop(p,l,r);
      |                                ^~~~
foodcourt.cpp: In member function 'void SegTree::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:61:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |   ^~
foodcourt.cpp:61:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |                                 ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11