Submission #386392

#	Time	Username	Problem	Language	Result	Execution time	Memory
386392		MatheusLealV	Food Court (JOI21_foodcourt)	C++17	100 / 100	745 ms	43880 KiB

foodcourt

#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define N 250020
// #define int long long
typedef long long ll;
#define pb push_back
using namespace std;
const ll inf = (ll)(2e15);
struct node{
	#define l (2*nod)
	#define r (2*nod + 1)
	#define mid ((a + b)/2)
	ll max1, max2;
	ll lazy;
	node(ll x = 0){
		max1 = x;
		max2 = -inf;
		lazy=0;
	}
} tree[4*N];

void merge(int nod){
	tree[nod].max1 = max(tree[l].max1, tree[r].max1);
	tree[nod].max2 = -inf;
	if(tree[l].max1 != tree[nod].max1) tree[nod].max2 = max(tree[nod].max2, tree[l].max1);
	if(tree[l].max2 != tree[nod].max1) tree[nod].max2 = max(tree[nod].max2, tree[l].max2);
	if(tree[r].max1 != tree[nod].max1) tree[nod].max2 = max(tree[nod].max2, tree[r].max1);
	if(tree[r].max2 != tree[nod].max1) tree[nod].max2 = max(tree[nod].max2, tree[r].max2);
}
void build(int nod, int a, int b){
	if(a == b){
		tree[nod] = node(0);
		return;
	}
	build(l, a, mid), build(r, mid + 1, b);
	merge(nod);
}
void propaga(int nod, int a, int b){
	if(a != b){
		if((tree[l].max1+tree[l].lazy) > tree[nod].max1){
			tree[l].max1 = tree[nod].max1-tree[l].lazy;
		}
		if(tree[r].max1+tree[r].lazy > tree[nod].max1){
			tree[r].max1 = tree[nod].max1-tree[r].lazy;
		}
		tree[l].lazy += tree[nod].lazy;
		tree[r].lazy += tree[nod].lazy;
	}
	tree[nod].max1 += tree[nod].lazy;
	tree[nod].max2 += tree[nod].lazy;
	tree[nod].lazy=0;
}
void upd(int nod, int a, int b, int i, int j, ll x){
	propaga(nod, a, b);
	if(j < a or i > b or tree[nod].max1 <= x) return;
	if(i <= a and j >= b and tree[nod].max1 > x and x > tree[nod].max2){
		tree[nod].max1 = x;
		return;
	}
	upd(l, a, mid, i, j, x);upd(r, mid + 1, b, i, j, x);
	merge(nod);
}
int L[N], R[N], C[N], K[N];

void upd2(int nod, int a, int b, int &tmp){
	propaga(nod,a,b);
	if(R[tmp]<a or L[tmp]>b)return;
	if(L[tmp]<=a and R[tmp] >= b){
		tree[nod].lazy -= K[tmp];
		propaga(nod,a,b);
		return;
	}
	upd2(l,a,mid,tmp),upd2(r,mid+1,b,tmp);
	merge(nod);
}
ll query(int nod, int a, int b, int i){
	propaga(nod, a, b);
	if(a==b) return tree[nod].max1;
	if(i <= mid) return query(l, a,mid,i);
	return query(r, mid + 1, b, i);
}
int n, m, q;
struct service{
	int i, st, en,id,ans;
	ll removed, b;
	service(int i1,ll removed1,ll b1,int st1,int en1,int id1,int ans1){
		i=i1;removed=removed1;b=b1;st=st1;en=en1;id=id1;ans=ans1;
	}
};
vector<service> Q;

ll bit[N];
void bit_upd(int x, ll v){
	assert(x!=0);
	for(int i = x; i < N; i += (i&-i)) bit[i]+=v;
}
ll bit_query(int x){
	assert(x!=0);
	ll sum = 0;
	for(int i =x;i>0;i-=(i&-i))sum+=bit[i];
	return sum;
}
vector<int> check[N];

ll seg[4*N], lazy[4*N];
ll w[N];
void build1(int nod, int a, int b){
	if(a==b){
		seg[nod] = Q[a].b + Q[a].removed;
		return; 
	}
	build1(l,a,mid);build1(r,mid+1,b);
	seg[nod]=min(seg[l], seg[r]);
}
void prop(int nod, int a, int b){
	seg[nod] += lazy[nod];
	if(a!=b){
		lazy[l]+=lazy[nod];
		lazy[r]+=lazy[nod];
	}
	lazy[nod]=0;
}

void tset(int nod,int a, int b,int &tmp){
	prop(nod, a, b);
	if(R[tmp]<Q[a].i or L[tmp]>Q[b].i) return;
	if(L[tmp]<=Q[a].i and R[tmp] >= Q[b].i){
		lazy[nod]-=K[tmp];
		prop(nod,a,b);
		return;
	}
	tset(l,a,mid,tmp);tset(r,mid+1,b, tmp);
	seg[nod]=min(seg[l],seg[r]);
}
int ans[N];
//look for values less than or equal to 0
void look(int nod, int a, int b, int &tmp){
	prop(nod,a,b);
	if(seg[nod] > 0) return;
	if(a==b){
		seg[nod] = inf;
		if(Q[a].en >= tmp)ans[Q[a].st]=C[tmp];
		return;
	}
	look(l,a,mid,tmp),look(r,mid+1,b,tmp);
	seg[nod]=min(seg[l], seg[r]);
}
int findL(int i){
	int st = 0, en = (int)Q.size() - 1,md,best=-1;
	while(en >= st){
		md=(st+en)/2;
		if(Q[md].i >= L[i]){
			best=md;
			en=md-1;
		}
		else st=md+1;
	}
	return best;
}
int findR(int i){
	int st = 0, en = (int)Q.size() - 1,md,best=-1;
	while(en >= st){
		md=(st+en)/2;
		if(Q[md].i <= R[i]){
			best=md;
			st = md + 1;;
		}
		else en=md-1;
	}
	return best;	
}
inline void fastscan(int &number) { 
    bool negative = false; 
    register int c; 
    number = 0; 
      c = getchar(); 
    if (c=='-') { 
        negative = true; 
  
        c = getchar(); 
    } 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
  
    if (negative) 
        number *= -1; 
}
inline void fastscanll(ll &number) { 
    bool negative = false; 
    register int c; 
    number = 0; 
      c = getchar(); 
    if (c=='-') { 
        negative = true; 
  
        c = getchar(); 
    } 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
  
    if (negative) 
        number *= -1; 
}
int main(){
	// ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	fastscan(n);fastscan(m);fastscan(q);
	for(int i = 0; i < 4*N; i++) tree[i] = node(0);
	build(1,1,n);
	int tmp = 0,j = 0,tm2=q+1;
	for(int i = 1, t, a,b ,c; i <= q; i++){
		fastscan(t);
		if(t == 1){
			++tmp;
			fastscan(L[tmp]);fastscan(R[tmp]);fastscan(C[tmp]);fastscan(K[tmp]);
			// cin>>L[tmp]>>R[tmp]>>C[tmp]>>K[tmp];
			upd2(1,1,n,tmp);
			// upd(1,1,n,L[tmp],R[tmp],0);
			bit_upd(L[tmp],K[tmp]);
			bit_upd(R[tmp]+1,-K[tmp]);
		}
		else if(t == 2){
			fastscan(a);fastscan(b);fastscan(c);
			// cin>>a>>b>>c;
			L[tm2]=a;R[tm2]=b;K[tm2]=-c;
			upd2(1,1,n,tm2);
			upd(1,1,n,1,n,0);
		}
		else{
			// upd(1,1,n,1,n,0);
			ll b;
			++j;
			fastscan(a);fastscanll(b);
			ll removed = bit_query(a)+query(1,1,n,a);
			Q.pb({a, removed, b, j, tmp,i,0});
		}
	}
	sort(Q.begin(), Q.end(), [&](auto a, auto b){
		return a.i<b.i;
	});

	build1(1,0,(int)(Q.size()) - 1);

	for(int i = 1; i <= tmp; i++){
		if(L[i]>=0 and R[i] >= 0) tset(1,0,(int)(Q.size()) - 1,i);
		if(L[i]>=0 and R[i] >= 0) look(1,0,(int)(Q.size()) - 1,i);
	}
	
	for(int i = 0; i < Q.size(); i++) printf("%d\n",ans[i+1]);
}

Compilation message (stderr)

foodcourt.cpp: In function 'void fastscan(int&)':
foodcourt.cpp:175:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  175 |     register int c;
      |                  ^
foodcourt.cpp: In function 'void fastscanll(ll&)':
foodcourt.cpp:191:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  191 |     register int c;
      |                  ^
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:249:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<service>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |  for(int i = 0; i < Q.size(); i++) printf("%d\n",ans[i+1]);
      |                 ~~^~~~~~~~~~

• 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