Submission #439018

#	Time	Username	Problem	Language	Result	Execution time	Memory
439018		kig9981	Food Court (JOI21_foodcourt)	C++17	100 / 100	971 ms	42376 KiB

foodcourt

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct Seg
{
	long long m, sm, lz, slz;
	Seg() : m(0), sm(0x7fffffffffffffffLL), lz(0), slz(-0x7fffffffffffffffLL) {}
	Seg &operator =(const Seg &a) {
		m=a.m;
		sm=a.sm;
		return *this;
	}
};

const int SZ=1<<18;
const long long MAX=0x7fffffffffffffffLL;
Seg tree[2*SZ];
vector<tuple<int,int,int>> U[250001];
vector<tuple<int,int,long long>> qry;
long long C[2*SZ];
int V[250000];

Seg combine(const Seg &a, const Seg &b)
{
	Seg c;
	c.m=min(a.m,b.m);
	if(c.m<max(a.m,b.m)) c.sm=max(a.m,b.m);
	if(c.m<a.sm) c.sm=min(c.sm,a.sm);
	if(c.m<b.sm) c.sm=min(c.sm,b.sm);
	return c;
}

void lazy_propagation(int bit, int s, int e)
{
	if(tree[bit].slz!=-MAX) {
		if(s<e) {
			if(max(tree[2*bit].slz,tree[2*bit].m)+tree[2*bit].lz==tree[bit].m) tree[2*bit].slz=tree[bit].slz-tree[2*bit].lz;
			if(max(tree[2*bit+1].slz,tree[2*bit+1].m)+tree[2*bit+1].lz==tree[bit].m) tree[2*bit+1].slz=tree[bit].slz-tree[2*bit+1].lz;
		}
		tree[bit].m=tree[bit].slz;
		tree[bit].slz=-MAX;
	}
	tree[bit].m+=tree[bit].lz;
	if(tree[bit].sm<MAX) tree[bit].sm+=tree[bit].lz;
	if(s<e) {
		tree[2*bit].lz+=tree[bit].lz;
		tree[2*bit+1].lz+=tree[bit].lz;
	}
	tree[bit].lz=0;
}

void add_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		tree[bit].lz=v;
		C[bit]+=max(v,0);
		lazy_propagation(bit,s,e);
		return;
	}
	add_tree(n1,n2,v,2*bit,s,m);
	add_tree(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}

void set_tree(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1 || tree[bit].m>=0) return;
	if(n1<=s && e<=n2 && tree[bit].sm>0) {
		tree[bit].slz=0;
		lazy_propagation(bit,s,e);
		return;
	}
	set_tree(n1,n2,2*bit,s,m);
	set_tree(n1,n2,2*bit+1,m+1,e);
	tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}

void update(int n, int c, int k)
{
	V[n]=c;
	for(C[n+=SZ]+=k;n>>=1;) C[n]=C[2*n]+C[2*n+1];
}

int query(long long k)
{
	int bit=1, s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(C[2*bit]<k) {
			k-=C[2*bit];
			s=m+1;
			bit=2*bit+1;
		}
		else {
			e=m;
			bit=2*bit;
		}
	}
	return V[s];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, Q, j=0;
	cin>>N>>M>>Q;
	for(int i=1;i<=Q;i++) {
		int t, a, c, d;
		long long b;
		cin>>t>>a>>b; --a;
		if(t==1) {
			cin>>c>>d;
			add_tree(a,--b,d);
			U[a].emplace_back(i,c,d);
			U[b+1].emplace_back(i,c,-d);
		}
		else if(t==2) {
			cin>>c;
			add_tree(a,--b,-c);
			set_tree(a,b);
		}
		else {
			long long tot;
			int n=1, s=0, e=SZ-1;
			while(s<e) {
				int m=(s+e)>>1;
				lazy_propagation(n,s,e);
				if(a<=m) tie(n,e)=make_pair(2*n,m);
				else tie(n,s)=make_pair(2*n+1,m+1);
			}
			lazy_propagation(n,s,e);
			if(tree[n].m<b) {
				qry.emplace_back(i,a,-1);
				continue;
			}
			for(tot=C[n=SZ+a];n>>=1;) tot+=C[n];
			qry.emplace_back(i,a,b+=tot-tree[SZ+a].m);
		}
	}
	sort(qry.begin(),qry.end(),[](const auto &a, const auto &b) {return get<1>(a)<get<1>(b);});
	memset(C,0,sizeof(C));
	for(auto &[t,p,v]: qry) {
		for(;j<=p;j++) for(auto[i,c,k]: U[j]) update(i,c,k);
		if(v==-1) {
			v=0;
			continue;
		}
		v=query(v);
	}
	sort(qry.begin(),qry.end());
	for(auto &[t,p,v]: qry) cout<<v<<'\n';
	return 0;
}

• 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: 11 / 11