Submission #688063

#	Time	Username	Problem	Language	Result	Execution time	Memory
688063		arnold518	Food Court (JOI21_foodcourt)	C++17	100 / 100	704 ms	44464 KiB

foodcourt

#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;

int N, M, Q;
int ans[MAXN+10];
pll B[MAXN+10];
vector<int> A[MAXN+10];

struct SEG
{
	pll tree[MAXN*4+10];
	void busy(int node, int tl, int tr)
	{
		if(tl!=tr)
		{
			tree[node*2].second=min(tree[node*2].second, tree[node*2].first+tree[node].second);
			tree[node*2].first+=tree[node].first;
			tree[node*2+1].second=min(tree[node*2+1].second, tree[node*2+1].first+tree[node].second);
			tree[node*2+1].first+=tree[node].first;
			tree[node]=pll(0, 0);
		}
	}
	void update(int node, int tl, int tr, int l, int r, ll k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			if(tl!=tr) tree[node]=pll(k, min(0ll, k));
			else
			{
				tree[node].second=min(tree[node].second, tree[node].first+k);
				tree[node].first+=k;
			}
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	ll query(int node, int tl, int tr, int pos)
	{
		busy(node, tl, tr);
		if(tl==tr) return tree[node].first-tree[node].second;
		int mid=tl+tr>>1;
		if(pos<=mid) return query(node*2, tl, mid, pos);
		else return query(node*2+1, mid+1, tr, pos);
	}
}seg, seg2;

struct SEG2
{
	ll tree[MAXN*4+10];
	void update(int node, int tl, int tr, int p, ll k)
	{
		if(tl==tr)
		{
			tree[node]+=k;
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p, k);
		else update(node*2+1, mid+1, tr, p, k);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
	int query(int node, int tl, int tr, ll k)
	{
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(tree[node*2]>=k) return query(node*2, tl, mid, k);
		else return query(node*2+1, mid+1, tr, k-tree[node*2]);
	}
}seg3;

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<=Q; i++)
	{
		int t, a, b, c, d; ll e;
		scanf("%d", &t);
		ans[i]=-1;
		if(t==1)
		{
			scanf("%d%d%d%d", &a, &b, &c, &d);
			seg.update(1, 1, N, a, b, d);
			seg2.update(1, 1, N, a, b, d);
			B[i]=pll(c, d);
			A[a].push_back(i);
			A[b+1].push_back(-i);
		}
		else if(t==2)
		{
			scanf("%d%d%d", &a, &b, &c);
			seg.update(1, 1, N, a, b, -c);
		}
		else
		{
			scanf("%d%lld", &a, &e);
			ans[i]=0;
			ll t=seg.query(1, 1, N, a);
			if(t>=e)
			{
				B[i]=pll(-1, seg2.query(1, 1, N, a)-(t-e));
				A[a].push_back(i+Q);
			}
		}
		//for(int j=1; j<=N; j++) printf("%lld ", seg2.query(1, 1, N, j)); printf("!\n");
	}

	for(int i=1; i<=N; i++)
	{
		sort(A[i].begin(), A[i].end());

		for(auto it : A[i])
		{
			if(it<0)
			{
				seg3.update(1, 1, Q, -it, -B[-it].second);
			}
			else if(it<=Q)
			{
				seg3.update(1, 1, Q, it, B[it].second);
			}
			else
			{
				ans[it-Q]=B[seg3.query(1, 1, Q, B[it-Q].second)].first;
			}
		}
	}

	for(int i=1; i<=Q; i++) if(ans[i]>=0) printf("%d\n", ans[i]);
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
foodcourt.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In member function 'll SEG::query(int, int, int, int)':
foodcourt.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In member function 'void SEG2::update(int, int, int, int, ll)':
foodcourt.cpp:67:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In member function 'int SEG2::query(int, int, int, ll)':
foodcourt.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int mid=tl+tr>>1;
      |           ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    scanf("%d%d%d%d", &a, &b, &c, &d);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d%d%d", &a, &b, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d%lld", &a, &e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• 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