Submission #421894

#	Time	Username	Problem	Language	Result	Execution time	Memory
421894		jamezzz	Food Court (JOI21_foodcourt)	C++17	0 / 100	143 ms	10652 KiB

foodcourt

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int,ll> ii;

#define maxn 250005

struct up{ int l,r,c;ll k; };
vector<up> ups;
struct qry{ int l,i;ll k; };
struct thing{
	int s,e;
	vector<qry> v;
};
queue<thing> qe;

int n,m,q,t,l,r,c,ans[maxn];
ll k,ft[650005];

void upd(int x,int y,ll v){
	while(x<=n)ft[x]+=v,x+=x&-x;
	++y;
	while(y<=n)ft[y]-=v,y+=y&-y;
}
ll query(int x){
	ll res=0;
	while(x)res+=ft[x],x-=x&-x;
	return res;
}

int main(){
	sf("%d%d%d",&n,&m,&q);
	thing th={0,0};
	for(int i=0;i<q;++i){
		sf("%d",&t);
		if(t==1){
			sf("%d%d%d%lld",&l,&r,&c,&k);
			ups.pb({l,r,c,k});
		}
		if(t==3){
			sf("%d%lld",&l,&k);
			th.v.pb({l,i+1,k});
		}
	}
	memset(ans,-1,sizeof ans);
	ups.pb({1,n,0,1000000000000000});
	th.e=ups.size()-1;
	qe.push(th);
	int pv=-1;
	while(!qe.empty()){
		thing th=qe.front();qe.pop();
		if(th.s==th.e){
			for(auto qq:th.v){
				ans[qq.i]=ups[th.s].c;
			}
			continue;
		}
		int m=(th.s+th.e)/2;
		thing nl={th.s,m},nr={m+1,th.e};
		if(m<pv){
			memset(ft,0,sizeof ft);
			pv=-1;
		}
		while(pv<m){
			++pv;
			upd(ups[pv].l,ups[pv].r,ups[pv].k);
		}
		for(auto qq:th.v){
			if(qq.k<=query(qq.l))nl.v.pb(qq);
			else nr.v.pb(qq);
		}
		if(nl.v.size()>0)qe.push(nl);
		if(nr.v.size()>0)qe.push(nr);
	}
	for(int i=1;i<=q;++i)if(ans[i]!=-1)pf("%d\n",ans[i]);
}

/*
3 5 6
1 2 3 5 2
1 1 2 2 4
3 2 3
3 1 2
1 2 3 4 2
3 3 2

3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

*/

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:38:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  sf("%d%d%d",&n,&m,&q);
      |    ^
foodcourt.cpp:41:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   sf("%d",&t);
      |     ^
foodcourt.cpp:43:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |    sf("%d%d%d%lld",&l,&r,&c,&k);
      |      ^
foodcourt.cpp:47:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |    sf("%d%lld",&l,&k);
      |      ^

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