Submission #423513

#	Time	Username	Problem	Language	Result	Execution time	Memory
423513		jamezzz	Food Court (JOI21_foodcourt)	C++17	100 / 100	887 ms	90416 KiB

foodcourt

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

#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

#define maxn 250005

struct node{
	int s,e,m;
	ll v,lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;v=0;lz=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		v+=lz;
		if(s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){
			lz+=nv;return;
		}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo();r->ppo();
		v=min(l->v,r->v);
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return min(l->qry(x,m),r->qry(m+1,y));
	}
}*root=new node(0,maxn),*tot=new node(0,maxn);

struct upd{
	int pos;
	ll val;
	int tm,tp;
};
vector<upd> v;

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

void up(int x,ll v){
	while(x<maxn)ft[x]+=v,x+=x&-x;
}
ll query(int x){
	ll res=0;
	while(x)res+=ft[x],x-=x&-x;
	return res;
}
int desc(ll v){
	int cur=0;
	for(int u=(1<<17);u!=0;u>>=1){
		if(cur+u<maxn&&ft[cur+u]<=v){
			cur+=u;
			v-=ft[cur];
		}
	}
	return cur;
}

int main(){
	sf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=q;++i){
		sf("%d",&t);
		if(t==1){
			sf("%d%d%d%lld",&l,&r,&c,&k);
			v.pb({l,k,i,0});
			v.pb({r+1,-k,i,0});
			id[i]=c;
		}
		if(t==2){
			sf("%d%d%lld",&l,&r,&k);
			v.pb({l,-k,i,1});
			v.pb({r+1,k,i,1});
		}
		if(t==3){
			sf("%d%lld",&l,&k);
			qry[l].pb({k,i});
		}
	}
	memset(ans,-1,sizeof ans);
	sort(all(v),[&](upd a,upd b){ return a.pos>b.pos; });
	for(int i=1;i<=n;++i){
		while(!v.empty()&&v.back().pos==i){
			root->up(v.back().tm,maxn,v.back().val);
			if(v.back().tp==0)up(v.back().tm,v.back().val);
			v.pop_back();
		}
		for(ii pr:qry[i]){
			ll num=root->qry(pr.se,pr.se)-root->qry(0,pr.se);
			//current size
			if(num<pr.fi)ans[pr.se]=0;
			else{
				ll tot=query(pr.se);
				pr.fi+=tot-num;//how many were removed
				int pos=desc(pr.fi-1);
				ans[pr.se]=id[pos+1];
			}
		}
	}
	for(int i=1;i<=q;++i)if(ans[i]!=-1)pf("%d\n",ans[i]);
}

/*
3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 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

10 5 100
1 1 1 1 1
2 1 1 2
1 1 1 1 1
2 1 1 2
1 1 1 1 1
2 1 1 2
3 1 1
1 1 1 5 5
1 1 1 5 5
2 1 1 3
3 1 1
*/

Compilation message (stderr)

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

• 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