Submission #960304

#	Time	Username	Problem	Language	Result	Execution time	Memory
960304		aaron_dcoder	Food Court (JOI21_foodcourt)	C++17	100 / 100	618 ms	77988 KiB

foodcourt

#define NDEBUG

#ifdef NDEBUG

#define dbg(TXT) (void)0;
#define dbgv(VAR) (void)0;
#define dbgfor if constexpr (false) for

#else

#define _GLIBCXX_DEBUG
#define dbg(TXT) cerr << TXT << "\n";
#define dbgv(VAR) cerr << #VAR << " = " << VAR <<", line "<< __LINE__ << '\n';
#define dbgfor for

#endif

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

using ll = long long;
using pll = pair<ll,ll>;
#define e0 first
#define e1 second

constexpr ll INFTY = 2e18;

struct segtree
{
	vector<ll> toadd;
	vector<ll> currfloor;

	segtree(ll n)
	{
		toadd.assign(4*n,0);
		currfloor.assign(4*n,0);
	}

	void add(ll val, ll base, ll baseforced, ll lseg, ll rseg, ll l, ll r, ll node)
	{
		currfloor[node] = max(currfloor[node],baseforced);
		if (rseg<l || r<lseg) return;

		if (lseg<=l && r<=rseg)
		{
			toadd[node]+=val;
			currfloor[node] = max(currfloor[node],base);
			currfloor[node]+=val;
			return;
		}


		ll mid = (l+r)/2;
		add(val, base-toadd[node], currfloor[node]-toadd[node], lseg, rseg, l,mid,node*2);
		add(val, base-toadd[node], currfloor[node]-toadd[node], lseg, rseg, mid+1,r,node*2+1);
		currfloor[node]=-INFTY;
	}

	ll get(ll x, ll l, ll r, ll node)
	{
		if (x<l || r<x) return 0;

		if (l==r)
		{
			return currfloor[node];
		}

		ll mid = (l+r)/2;
		return max(toadd[node]+(get(x, l,mid,node*2)+get(x, mid+1,r,node*2+1)),currfloor[node]);
	}
};

struct segtree2
{
	vector<ll> rsum;
	segtree2(ll n)
	{
		rsum.assign(4*n,0);
	}

	void update(ll x, ll val, ll l, ll r, ll node)
	{
		if (x<l || r<x) return;
		if (l==r)
		{
			assert(l==x);
			rsum[node]=val;
			return;
		}

		ll mid = (l+r)/2;
		update(x, val, l,mid,node*2);
		update(x, val, mid+1,r,node*2+1);
		rsum[node]=rsum[node*2]+rsum[node*2+1];
	}

	ll preflb(ll val, ll l, ll r, ll node)
	{
		if (rsum[node]<val) return -1;

		if (l==r)
		{
			return l;
		}

		ll mid = (l+r)/2;
		ll lnode = preflb(val, l,mid,node*2);

		if (lnode!=-1) return lnode;

		return preflb(val-rsum[node*2], mid+1,r,node*2+1);
	}
};

int main()
{
	ll N,M,Q;
	cin >> N >> M >> Q;


	segtree stree(N);
	segtree totsize(N);

	vector<vector<pll>> tofind(N+1,vector<pll>{});
	vector<vector<pll>> tostart(N+1,vector<pll>{});
	vector<vector<ll>> toend(N+1,vector<ll>{});
	vector<ll> q_group(Q,-1);

	vector<ll> ans(Q,-1);


	for (ll qno = 0; qno < Q; ++qno)
	{
		ll t;
		cin >> t;

		if (t==1)
		{
			ll l,r,k;
			cin >> l >> r >> q_group[qno] >> k;

			tostart[l].push_back({k,qno});
			toend[r].push_back(qno);

			totsize.add(k,0,-INFTY,l,r, 1,N,1);
			stree.add(k,0,-INFTY,l,r, 1,N,1);
		}
		else if (t==2)
		{
			ll l,r,k;
			cin >> l >> r >> k;
			stree.add(-k,k,-INFTY,l,r, 1,N,1);
		}
		else
		{
			assert(t==3);
			ll a,b;
			cin >> a >> b;
			if (b>stree.get(a, 1,N,1))
			{
				ans[qno]=0;
			}
			else
			{
				tofind[a].push_back({totsize.get(a, 1,N,1)-(stree.get(a, 1,N,1)-b),qno});
			}
		}
	}

	//vector<ll> currpeeps(Q,0);
	segtree2 currpeeps(Q);
	for (ll i = 1; i <= N; ++i)
	{
		for (auto [k ,qno] :tostart[i])
		{
			//assert(currpeeps[qno]==0);
			currpeeps.update(qno, k, 0,Q-1,1);
		}

		for (auto [numpeeps, qno]:tofind[i])
		{
			/*ll cs=0;
			ll qidx=0;
			while (cs<numpeeps)
			{
				cs+=currpeeps[qidx];
				qidx++;
			}
			qidx--;*/
			ll qidx = currpeeps.preflb(numpeeps, 0,Q-1,1);
			ans[qno]=q_group[qidx];
		}
		

		for (ll qno :toend[i])
		{
			//assert(currpeeps[qno]!=0);
			//currpeeps[qno]=0;
			currpeeps.update(qno, 0, 0,Q-1,1);
		}
	}

	for (ll i : ans)
	{
		if (i!=-1) cout << i << "\n";
	}
}

• 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