Submission #442360

#	Time	Username	Problem	Language	Result	Execution time	Memory
442360		keta_tsimakuridze	Food Court (JOI21_foodcourt)	C++14	100 / 100	763 ms	58680 KiB

foodcourt

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define int long long
#define pii pair<ll,ll> 
using namespace std;
const int N=250005,mod=1e9+7;
int t,n,m,q,g[N],ans[N];
ll tree[4*N],add[4*N],cnt[N],tr[4*N];
pii lazy[4*N];
vector<int> t1;
vector<pair<ll,int> > st[N],en[N],x[N];

void update2(int u,int ind,int l,int r,int val) {
	if(l>ind || r<ind) return;
	if(l==r) {
		tr[u]+=val; 
		return;
	}
	int mid = (l+r)/2;
	update2(2*u,ind,l,mid,val);
	update2(2*u+1,ind,mid+1,r,val);
	tr[u] = tr[2*u] + tr[2*u+1];
}
int getans2(int u,int l,int r,int c) {
	if(l==r)  return l;
	int mid = (l+r)/2;
	if(tr[2*u] >= c) return getans2(2*u,l,mid,c);
	else return getans2(2*u+1,mid+1,r,c - tr[2*u]);
}
int getans1(int u,int start,int end,int l,int r){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) return tr[u];
	int mid = (l+r)/2;
	return getans1(2*u,start,end,l,mid) + getans1(2*u+1,start,end,mid+1,r);
}
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);
}
ll 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  {
			ll 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++) {
			update2(1,st[i][j].f,1,q,st[i][j].s);// cout<<"++"<<st[i][j].f<<"__"<<st[i][j].s<<endl;
		}
		for(int j=0;j<x[i].size();j++) {
			int ind = x[i][j].s; 
			ll c = getans1(1,1,ind,1,q);
			if(cnt[ind] < x[i][j].f) {
				ans[ind] = -1;
				continue;
			}
			else {
			
				ans[ind] = g[getans2(1,1,q,c - (cnt[ind] - x[i][j].f+1)+1)];
			//	cout<<ind<<" "<<c<<"__"<<getans2(1,1,q,c-(cnt[ind]-x[i][j].f+1)+1)<<endl;
			}
		}
		for(int j=0;j<en[i].size();j++){
			update2(1,en[i][j].f,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:86:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 |  main(){
      |  ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:115: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]
  115 |   for(int j=0;j<st[i].size();j++) {
      |               ~^~~~~~~~~~~~~
foodcourt.cpp:118: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]
  118 |   for(int j=0;j<x[i].size();j++) {
      |               ~^~~~~~~~~~~~
foodcourt.cpp:131: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]
  131 |   for(int j=0;j<en[i].size();j++){
      |               ~^~~~~~~~~~~~~

• 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