제출 #422630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422630		jamezzz	푸드 코트 (JOI21_foodcourt)	C++17	0 / 100	940 ms	73344 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#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 emplace_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<int, 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 lzadd,lzmx,v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;v=0;lzadd=0;lzmx=-1;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		if(lzmx!=-1){
			if(s==e)mxto(v,lzmx);
			else{
				if(l->lzadd!=0)l->ppo();
				if(r->lzadd!=0)r->ppo();
				mxto(l->lzmx,lzmx);
				mxto(r->lzmx,lzmx);
			}
			lzmx=-1;
		}
		else{
			if(s==e)v+=lzadd;
			else{
				if(l->lzmx!=-1)l->lzmx+=lzadd;
				else l->lzadd+=lzadd;
				if(r->lzmx!=-1)r->lzmx+=lzadd;
				else r->lzadd+=lzadd;
			}
			lzadd=0;
		}
	}
	void radd(int x,int y,ll nv){
		if(s==x&&e==y){
			if(lzmx!=-1)lzmx+=nv;
			else lzadd+=nv;
			return;
		}
		if(y<=m)l->radd(x,y,nv);
		else if(x>m)r->radd(x,y,nv);
		else l->radd(x,m,nv),r->radd(m+1,y,nv);
	}
	void rmxto(int x,int y,ll nv){
		if(s==x&&e==y){
			if(lzadd!=0)ppo();
			mxto(lzmx,nv);
			return;
		}
		if(y<=m)l->rmxto(x,y,nv);
		else if(x>m)r->rmxto(x,y,nv);
		else l->rmxto(x,m,nv),r->rmxto(m+1,y,nv);
	}
	ll qry(int x){
		ppo();
		if(s==x&&e==x)return v;
		if(x<=m)return l->qry(x);
		else return r->qry(x);
	}
}*tot,*cur;

struct fw{
	ll n,ft[250005];
	void up(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 qry(int x){
		ll res=0;
		while(x)res+=ft[x],x-=x&-x;
		return res;
	}
}ft;

struct thing{
	int s,e;vi v;
};
queue<thing> bsta;

int n,m,q,t[maxn],l[maxn],r[maxn],c[maxn],ans[maxn];
vector<int> ups;
ll k[maxn];

int main(){
	sf("%d%d%d",&n,&m,&q);
	tot=new node(1,n);
	cur=new node(1,n);
	thing th={0,0};
	for(int i=0;i<q;++i){
		sf("%d",&t[i]);
		if(t[i]==1){
			sf("%d%d%d%lld",&l[i],&r[i],&c[i],&k[i]);
			tot->radd(l[i],r[i],k[i]);
			cur->radd(l[i],r[i],k[i]);
			ups.pb(i);
		}
		else if(t[i]==2){
			sf("%d%d%lld",&l[i],&r[i],&k[i]);
			cur->radd(l[i],r[i],-k[i]);
			cur->rmxto(l[i],r[i],0);
		}
		else{
			sf("%d%lld",&l[i],&k[i]);
			ll rem=tot->qry(l[i])-cur->qry(l[i]);
			k[i]+=rem;
			th.v.pb(i);
		}
	}
	th.e=ups.size();
	bsta.push(th);
	ft.n=n;
	int pv=-1;
	while(!bsta.empty()){
		thing x=bsta.front();bsta.pop();
		if(x.s==x.e){
			for(int i:x.v){
				if(x.s==sz(ups))ans[i]=0;
				else ans[i]=c[ups[x.s]];
			}
			continue;
		}
		int m=(x.s+x.e)/2;
		thing nl={x.s,m},nr={m+1,x.e};
		if(m<pv)memset(ft.ft,0,sizeof ft.ft),pv=-1;
		while(pv<m){
			++pv;
			ft.up(l[ups[pv]],r[ups[pv]],k[ups[pv]]);
		}
		for(int i:x.v){
			if(k[i]<=ft.qry(l[i]))nl.v.pb(i);
			else nr.v.pb(i);
		}
		if(sz(nl.v)>0)bsta.push(nl);
		if(sz(nr.v)>0)bsta.push(nr);
	}
	for(int i=0;i<q;++i){
		if(t[i]==3)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
*/

컴파일 시 표준 에러 (stderr) 메시지

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

• 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