Submission #442313

#	Time	Username	Problem	Language	Result	Execution time	Memory
442313		keta_tsimakuridze	Food Court (JOI21_foodcourt)	C++14	68 / 100	1026 ms	57632 KiB

foodcourt

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int> 
using namespace std;
const int N=250005,mod=1e9+7;
int t,tree[4*N],add[4*N],n,m,q,g[N],cnt[N],ans[N];
pii lazy[4*N];
vector<int> t1;
vector<pair<int,int> > st[N],en[N],x[N];
void update1(int u,int start,int end,int l,int r,int val) {
	if(l>end || r<start) return;
	if(start<=l && r<=end) {
		add[u] += val;
		return;
	}
	if(l==r) return;
	int mid = (l+r)/2;
	update1(2*u,start,end,l,mid,val);
	update1(2*u+1,start,end,mid+1,r,val);
}
int getans1(int u,int ind,int l,int r) {
	if(l>ind || r<ind) return 0;
	if(l==r) return add[u];
	int mid = (l+r)/2;
	return getans1(2*u,ind,l,mid) + getans1(2*u+1,ind,mid+1,r) + add[u];
}
void upd(pii &a,pii b){
	if(a.s >= b.f) {
		a.s = a.s - b.f + b.s;
	}
	else {
		a.f += b.f - a.s;
		a.s = b.s;
	}
}
void update(int u,int start,int end,int l,int r,int val) {
	if(lazy[u].f||lazy[u].s) {
		tree[u] = max(tree[u]-lazy[u].f,0ll) + lazy[u].s;
		if(l!=r){
			upd(lazy[2*u],lazy[u]);
			upd(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = {0,0};
	}
	if(l>end || r<start) return;
	if(start<=l && r<=end) {
		if(val>0) lazy[u].s = val;
		else lazy[u].f = -val; 
		tree[u] = max(tree[u]-lazy[u].f,0ll) + lazy[u].s;
		if(l!=r){
			upd(lazy[2*u],lazy[u]);
			upd(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = {0,0};
		return;		
	}
	int mid = (l+r)/2;
	update(2*u,start,end,l,mid,val);
	update(2*u+1,start,end,mid+1,r,val);
}
int getans(int u,int ind,int l,int r) {
	if(lazy[u].f||lazy[u].s) {
		tree[u] = max(tree[u]-lazy[u].f,0ll) + lazy[u].s;
		if(l!=r){
			upd(lazy[2*u],lazy[u]);
			upd(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = {0,0};
	}
	if(l>ind || r<ind) return 0;
	if(l==r) return tree[u];
	int mid = (l+r)/2;
	return getans(2*u,ind,l,mid) + getans(2*u+1,ind,mid+1,r);
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		int t,l,r,c,k;
		cin>>t;
		
		if(t==1) {
			
			cin>>l>>r>>c>>k;
			g[i] = c;
			st[l].push_back({i,k});
			en[r].push_back({i,k});
			update(1,l,r,1,n,k);
			t1.push_back(i);
		}
		else if(t==2){
			cin>>l>>r>>k;
			update(1,l,r,1,n,-k);
		}
		else  {
			int a,c;
			cin>>a>>c;
			x[a].push_back({c,i});
			cnt[i] = getans(1,a,1,n);  
		}
	} 
	for(int i=1;i<=n;i++) {
		for(int j=0;j<st[i].size();j++) {
			update1(1,st[i][j].f,q,1,q,st[i][j].s); 
		}
		for(int j=0;j<x[i].size();j++) {
			int ind = x[i][j].s; 
			int c = getans1(1,ind,1,q);
			if(cnt[ind] < x[i][j].f) {
				ans[ind] = -1;
				continue;
			}
			else {
				int l = 0, r = (int)t1.size() - 1; 
				while(l<=r) {
					int mid = (l+r)/2; 
					if(c - getans1(1,t1[mid]-1,1,q) >= cnt[ind] - x[i][j].f+1) {
						ans[ind] = g[t1[mid]];  
						l = mid + 1;
					}
					else r = mid - 1;
				}
				
			}
		}
		for(int j=0;j<en[i].size();j++){
			update1(1,en[i][j].f,q,1,q,-en[i][j].s); 
		}
	}
	for(int i=1;i<=q;i++) {
		if(ans[i]) cout<<max(0ll,ans[i])<<" ";
	}
}

Compilation message (stderr)

foodcourt.cpp:77:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 |  main(){
      |  ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:105:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int j=0;j<st[i].size();j++) {
      |               ~^~~~~~~~~~~~~
foodcourt.cpp:108:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int j=0;j<x[i].size();j++) {
      |               ~^~~~~~~~~~~~
foodcourt.cpp:128:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(int j=0;j<en[i].size();j++){
      |               ~^~~~~~~~~~~~~

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