Submission #386398

#	Time	Username	Problem	Language	Result	Execution time	Memory
386398		haojiandan	Food Court (JOI21_foodcourt)	C++14	89 / 100	1004 ms	50400 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=250010;
int n,m,q;
ll mn[maxn*4],mx[maxn*4],lazy[maxn*4];
int tim[maxn*4],T[maxn*4];
struct node {
	int op,l,r,c; ll k;
} Q[maxn];
int tot,tot2,zero[maxn*4];
ll all[maxn];
struct Node {
	int l,r,id;
} st[maxn],st2[maxn];
int pos[maxn],res[maxn],now;
void puttag(int root,ll delta) {
	lazy[root]+=delta,mn[root]+=delta,mx[root]+=delta;
	mn[root]=max(mn[root],0LL),mx[root]=max(mx[root],0LL);
}
void pushdown(int root) {
	if (zero[root]) {
		zero[root<<1]=zero[root<<1|1]=1;
		zero[root]=0;
		mx[root<<1]=mn[root<<1]=mx[root<<1|1]=mn[root<<1|1]=0;
		lazy[root<<1]=lazy[root<<1|1]=0;
	}
	if (lazy[root]) {
		puttag(root<<1,lazy[root]);
		puttag(root<<1|1,lazy[root]);
		lazy[root]=0;
	}
	if (T[root]) {
		tim[root<<1]=max(tim[root<<1],T[root]);
		T[root<<1]=max(T[root<<1],T[root]);
		tim[root<<1|1]=max(tim[root<<1|1],T[root]);
		T[root<<1|1]=max(T[root<<1|1],T[root]);
		T[root]=0;
	}
}
void pushup(int root) {
	mn[root]=min(mn[root<<1],mn[root<<1|1]);
	mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
void add(int L,int R,int l,int r,int root,ll delta,int flag) {
	if (L<=l&&r<=R) {
		if (!flag) {
			puttag(root,delta);
		}
		if (mn[root]==0) {
			if (mx[root]==0) {
				tim[root]=T[root]=now;
				lazy[root]=0; zero[root]=1;
			} else {
				int mid=(l+r)>>1;
				pushdown(root);
				add(L,R,l,mid,root<<1,delta,1);
				add(L,R,mid+1,r,root<<1|1,delta,1);
			}
		}
		return;
	}
	pushdown(root); int mid=(l+r)>>1;
	if (L<=mid) add(L,R,l,mid,root<<1,delta,flag);
	if (mid<R) add(L,R,mid+1,r,root<<1|1,delta,flag);
	pushup(root);
}
int query(int x,int l,int r,int root) {
	if (l==r) return tim[root];
	int mid=(l+r)>>1; pushdown(root);
	if (x<=mid) return query(x,l,mid,root<<1);
	return query(x,mid+1,r,root<<1|1);
}
namespace BIT {
	ll tr[maxn];
	void add(int x,ll delta) {
		for (;x<=n;x+=x&(-x)) tr[x]+=delta;
	}
	ll query(int x) {
		ll res=0;
		for (;x;x-=x&(-x)) res+=tr[x];
		return res;
	}
	void add(int l,int r,ll delta) {
		add(l,delta),add(r+1,-delta);
	}
	void clear() { for (int i=1;i<=n;i++) tr[i]=0; }
};
namespace Seg {
	ll add[maxn*4],tr[maxn*4],mx[maxn*4];
	bool bz[maxn*4];
	void mark(int root,int op,ll delta) {
		if (op==1) add[root]+=delta,tr[root]+=delta;
		else {
			tr[root]=max(tr[root],delta);
			delta-=add[root];
			if (bz[root]) mx[root]=max(mx[root],delta);
			else bz[root]=1,mx[root]=delta;
		}
	}
	void pushdown(int root) {
		if (bz[root]) {
			mark(root<<1,0,mx[root]);
			mark(root<<1|1,0,mx[root]);
			mx[root]=bz[root]=0;
		}
		if (add[root]) {
			mark(root<<1,1,add[root]);
			mark(root<<1|1,1,add[root]);
			add[root]=0;
		}
	}
	void addd(int L,int R,int l,int r,int root,int op,ll delta) {
		if (L<=l&&r<=R) {
			mark(root,op,delta);
			return;
		}
		pushdown(root); int mid=(l+r)>>1;
		if (L<=mid) addd(L,R,l,mid,root<<1,op,delta);
		if (mid<R) addd(L,R,mid+1,r,root<<1|1,op,delta);
		tr[root]=max(tr[root<<1],tr[root<<1|1]);
	}
	ll query(int x,int l,int r,int root) {
		if (l==r) return tr[root];
		int mid=(l+r)>>1; pushdown(root);
		if (x<=mid) return query(x,l,mid,root<<1);
		return query(x,mid+1,r,root<<1|1);
	}
};
vector<pair<int,int> > g[maxn];
ll buc[maxn],haha[maxn];
int main() {
	//freopen("1.txt","r",stdin);
	read(n),read(m),read(q);
	int op,l,r,c,mid; ll tmp,k;
	if (m==1) {
		for (int i=1;i<=q;i++) {
			now=i;
			read(op);
			if (op==1) {
				read(l),read(r),read(c),read(k);
				Seg::addd(l,r,1,n,1,1,k);
			} else if (op==2) {
				read(l),read(r),read(k); c=0;
				Seg::addd(l,r,1,n,1,1,-k);
				Seg::addd(1,n,1,n,1,2,0);
			} else {
				read(c),read(k); l=r=0;
				tmp=Seg::query(c,1,n,1);
				if (tmp>=k) puts("1");
				else puts("0");
			}
		}
		exit(0);
	}
	for (int i=1;i<=q;i++) {
		now=i;
		read(op);
		if (op==1) {
			read(l),read(r),read(c),read(k);
			add(l,r,1,n,1,k,0);
		} else if (op==2) {
			read(l),read(r),read(k); c=0;
			add(l,r,1,n,1,-k,0);
		} else {
			read(c),read(k); l=r=0;
			pos[i]=query(c,1,n,1);
		//	printf("%d\n",pos[i]);
		}
		Q[i]=(node){op,l,r,c,k};
	}

	//puts("");
	
	
	for (int i=1;i<=q;i++) if (Q[i].op==3) {
		st[++tot]=(Node){pos[i]+1,i,i};
		l=pos[i]+1,r=i;
		if (l>1) g[l-1].push_back(make_pair(i,-1));
		g[r].push_back(make_pair(i,1));
	}
	for (int i=1;i<=q;i++) {
		if (Q[i].op==2) BIT::add(Q[i].l,Q[i].r,Q[i].k);
		for (pair<int,int> A : g[i]) {
			all[A.first]+=BIT::query(Q[A.first].c)*A.second;
		}
	}
	BIT::clear(); for (int i=1;i<=q;i++) g[i].clear();
	for (int i=1;i<=q;i++) if (Q[i].op==3) {
		g[pos[i]].push_back(make_pair(i,0));
	}
	for (int i=1;i<=q;i++) {
		if (Q[i].op==1) BIT::add(Q[i].l,Q[i].r,Q[i].k);
		for (pair<int,int> A : g[i]) {
			haha[A.first]+=BIT::query(Q[A.first].c);
		}
	}
	
	//for (int i=1;i<=q;i++) if (Q[i].op==3) printf(" %lld %lld\n",all[i],haha[i]);
	
	while (tot) {
		now=0; for (int i=1;i<=q;i++) g[i].clear();
		BIT::clear();
		for (int i=1;i<=tot;i++) {
			l=st[i].l,r=st[i].r,mid=(l+r)>>1;
			//if (pos[st[i].id]>0) g[pos[st[i].id]].push_back(make_pair(i,-1));
			g[mid].push_back(make_pair(i,1));
			buc[i]=0;
		}
		for (int i=1;i<=q;i++) {
			if (Q[i].op==1) BIT::add(Q[i].l,Q[i].r,Q[i].k);
			for (pair<int,int> A : g[i]) {
				buc[A.first]+=BIT::query(Q[st[A.first].id].c)*A.second;
			}
		}
		for (int i=1;i<=tot;i++) {
			l=st[i].l,r=st[i].r,mid=(l+r)>>1;
			//printf("%d %d %d %d %lld\n",st[i].id,l,r,mid,buc[i]);
			if (buc[i]-haha[st[i].id]-all[st[i].id]>=Q[st[i].id].k) res[st[i].id]=mid,r=mid-1;
			else l=mid+1;
			if (l<=r) st2[++tot2]=(Node){l,r,st[i].id};
		}
		tot=tot2; tot2=0;
		for (int i=1;i<=tot;i++) st[i]=st2[i];
		
	}
	for (int i=1;i<=q;i++) if (Q[i].op==3) printf("%d\n",Q[res[i]].c);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

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