Submission #396433

#	Time	Username	Problem	Language	Result	Execution time	Memory
396433		arnold518	Food Court (JOI21_foodcourt)	C++17	68 / 100	1028 ms	53924 KiB

foodcourt

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 25e4;
const int MAXQ = 25e4;

int N, M, Q;

pll operator + (pll p, pll q)
{
	if(p.second>q.first)
	{
		p.second-=q.first;
		p.second+=q.second;
	}
	else
	{
		p.first+=q.first-p.second;
		p.second=q.second;
	}
	return p;
}

struct SEG
{
	ll A[MAXN+10];
	pll lazy[MAXN*4+10];

	void busy(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			A[tl]=max(0ll, A[tl]-lazy[node].first);
			A[tl]+=lazy[node].second;
		}
		else
		{
			lazy[node*2]=lazy[node*2]+lazy[node];
			lazy[node*2+1]=lazy[node*2+1]+lazy[node];
		}
		lazy[node]=pll(0, 0);
	}

	void update(int node, int tl, int tr, int l, int r, pll p)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			lazy[node]=p;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, p);
		update(node*2+1, mid+1, tr, l, r, p);
	}

	void query(int node, int tl, int tr, int p)
	{
		busy(node, tl, tr);
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(p<=mid) query(node*2, tl, mid, p);
		else query(node*2+1, mid+1, tr, p);
	}
}seg;

struct Data
{
	int t, l, r, c, a, p;
	ll k, b;
};

struct BIT
{
	ll tree[MAXN+10];
	void init()
	{
		for(int i=1; i<=N; i++) tree[i]=0;
	}
	void update(int i, ll k)
	{
		for(; i<=N; i+=(i&-i)) tree[i]+=k;
	}
	ll query(int i)
	{
		ll ret=0;
		for(; i>0; i-=(i&-i)) ret+=tree[i];
		return ret;
	}
	void update(int l, int r, ll k)
	{
		update(l, k);
		update(r+1, -k);
	}
}bit;

Data B[MAXN+10];

int lo[MAXN+10], hi[MAXN+10];
vector<pii> VVV[MAXN+10];
ll P[MAXN+10];

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	vector<Data> V;
	for(int p=1; p<=Q; p++)
	{
		int t;
		scanf("%d", &t);
		B[p].t=t; B[p].p=p;
		if(t==1)
		{
			int l, r, c, k;
			scanf("%d%d%d%d", &l, &r, &c, &k);
			B[p].l=l; B[p].r=r; B[p].c=c; B[p].k=k;
			seg.update(1, 1, N, l, r, {0, k});
			bit.update(l, r, k);
		}
		if(t==2)
		{
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			B[p].l=l; B[p].r=r; B[p].k=k;
			seg.update(1, 1, N, l, r, {k, 0});	
		}
		if(t==3)
		{
			int a; ll b;
			scanf("%d%lld", &a, &b);
			B[p].a=a;
			seg.query(1, 1, N, a);
			ll t=seg.A[a];
			b=bit.query(a)-t+b;
			B[p].b=b;
		}
	}

	for(int i=1; i<=Q; i++)
	{
		if(B[i].t==3)
		{
			lo[i]=0;
			hi[i]=i;
		}
	}

	while(1)
	{
		vector<pii> VV;
		for(int i=1; i<=Q; i++)
		{
			if(B[i].t==3)
			{	
				if(lo[i]+1<hi[i])
				{
					VVV[lo[i]+hi[i]>>1].push_back({lo[i]+hi[i]>>1, i});
				}
			}
		}
		for(int i=0; i<=Q; i++)
		{
			for(auto it : VVV[i])
			{
				VV.push_back(it);
			}
			VVV[i].clear();
		}
		if(VV.empty()) break;
		bit.init();
		for(int i=0, j=1; i<VV.size(); i++)
		{
			for(; j<=VV[i].first && j<=Q; j++)
			{
				if(B[j].t!=1) continue;
				bit.update(B[j].l, B[j].r, B[j].k);
			}
			if(bit.query(B[VV[i].second].a)>=B[VV[i].second].b)
			{
				hi[VV[i].second]=VV[i].first;
			}
			else
			{
				lo[VV[i].second]=VV[i].first;
			}
		}
	}
	for(int i=1; i<=Q; i++)
	{
		if(B[i].t==3)
		{
			//printf("%d %d\n", lo[i], hi[i]);
			if(B[hi[i]].t!=1) printf("0\n");
			else printf("%d\n", B[hi[i]].c);
		}
	}
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void SEG::update(int, int, int, int, int, pll)':
foodcourt.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In member function 'void SEG::query(int, int, int, int)':
foodcourt.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:167:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |      VVV[lo[i]+hi[i]>>1].push_back({lo[i]+hi[i]>>1, i});
      |          ~~~~~^~~~~~
foodcourt.cpp:167:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |      VVV[lo[i]+hi[i]>>1].push_back({lo[i]+hi[i]>>1, i});
      |                                     ~~~~~^~~~~~
foodcourt.cpp:181:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |   for(int i=0, j=1; i<VV.size(); i++)
      |                     ~^~~~~~~~~~
foodcourt.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |    scanf("%d%d%d%d", &l, &r, &c, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |    scanf("%d%d%d", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:140:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |    scanf("%d%lld", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

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