Submission #1253360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253360		thdh__	Food Court (JOI21_foodcourt)	C++20	100 / 100	459 ms	90228 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 3e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

struct node {
	int sum, suma, sumb;
	ii mn;
};

node merge(node a, node b) 
{
	node res;
	res.sum = a.sum + b.sum;
	res.suma = a.suma + b.suma;
	res.sumb = b.sumb + a.sumb;
	res.mn = min(a.mn, {a.sum + b.mn.fi, b.mn.se});
	return res;
}

int n,m,q;
int type[N], a[N], b[N], c[N], k[N], ans[N];
vector<int> s[N], e[N], qu[N];
node st[4*N];

node def(int pos) // default node
{
	node res;
	res.sum = res.suma = res.sumb = 0;
	res.mn = {inf,pos};
	return res;
}

void build(int id,int l,int r) 
{
	if (l == r) 
	{
		st[id] = def(l);
		return;
	}
	int mid = l+r>>1;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	st[id] = merge(st[id*2], st[id*2+1]);
}

void update1(int id,int l,int r,int x) // turn on node
{
	if (l > x || r < x) return;
	if (l == r) 
	{
		if (type[l] == 1)
		{
			st[id].sum = k[l]; 
			st[id].suma = k[l], st[id].sumb = 0;
			st[id].mn = {k[l], l};
		} else 
		{
			st[id].sum = -k[l]; 
			st[id].suma = 0, st[id].sumb = k[l];
			st[id].mn = {-k[l], l};
		}
		return; 
	}
	int mid = l+r>>1;
	update1(id*2,l,mid,x); update1(id*2+1,mid+1,r,x);
	st[id] = merge(st[id*2], st[id*2+1]);
}

void update2(int id,int l,int r,int x) // turn off node
{
	if (l > x || r < x) return;
	if (l == r) 
	{
		st[id] = def(l);
		return; 
	}
	int mid = l+r>>1;
	update2(id*2,l,mid,x); update2(id*2+1,mid+1,r,x);
	st[id] = merge(st[id*2], st[id*2+1]);
}

node query(int id,int l,int r,int u,int v) 
{
	if (u > v) return def(0);
	if (l > v || r < u) return def(0);
	if (u <= l && r <= v) return st[id];
	node res = def(0);
	int mid = l+r>>1;
	res = merge(res,query(id*2,l,mid,u,v)); res = merge(res,query(id*2+1,mid+1,r,u,v));
	return res;
}	

int get(int id,int l,int r,int x) 
{
	if (st[id].suma < x) return 0;
	if (l == r) return l;
	int mid = l+r>>1;
	int le = get(id*2,l,mid,x);
	if (le) return le;
	else return get(id*2+1,mid+1,r,x - st[id*2].suma);
}

void solve()
{
	cin>>n>>m>>q;
	for (int i=1;i<=q;i++) 
	{
		cin>>type[i];
		int l,r;
		if (type[i] == 1) cin>>l>>r>>c[i]>>k[i];
		else if (type[i] == 2) cin>>l>>r>>k[i];
		else cin>>a[i]>>b[i];
		if (type[i] != 3) 	
		{
			s[l].pb(i); e[r+1].pb(i);
		} else qu[a[i]].pb(i);
	}
	build(1,1,q);
	for (int i=1;i<=n;i++) {
		// turn on
		for (auto x : s[i]) update1(1,1,q,x);
		// turn off
		for (auto x : e[i]) update2(1,1,q,x);
		//query
		for (auto x : qu[i]) 
		{
			node tmp = query(1,1,q,1,x);
			int pos = 0;
			// cout<<x<<" "<<tmp.sum<<endl;
			if (tmp.mn.fi < 0) pos = tmp.mn.se;
			node l = query(1,1,q,1,pos), r = query(1,1,q,pos+1,x);
			if (r.sum < b[x]) ans[x] = 0;
			else ans[x] = c[get(1,1,q,b[x] + l.suma + r.sumb)];
		}
	}
	// cout<<endl;
	for (int i=1;i<=q;i++) if (type[i] == 3) cout<<ans[i]<<endl;
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
		cout<<"\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