Submission #416203

#	Time	Username	Problem	Language	Result	Execution time	Memory
416203		alireza_kaviani	Food Court (JOI21_foodcourt)	C++11	100 / 100	685 ms	64720 KiB

foodcourt

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())
#define lc							id << 1
#define rc							lc | 1

const ll MAXN = 25e4 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

struct query{
	int type , l , r;
	ll val;
};

int n , m , q , col[MAXN];
ll fen[MAXN] , mn[MAXN << 2] , seg[MAXN << 2] , lz2[MAXN << 2] , ans[MAXN];
pll lz[MAXN << 2];
vector<pll> vec[MAXN << 2];
vector<query> Q = {{0 , 0 , 0 , 0}};

void add(int x , int val){
	for( x++ ; x < MAXN ; x += x & -x)	fen[x] += val;
}

ll get(int x){
	ll ans = 0;
	for( x++ ; x ; x -= x & -x)	ans += fen[x];
	return ans;
}

void apply(int id , pll val){
	mn[id] = max(mn[id] + val.X , val.Y);
	lz[id].X += val.X;
	lz[id].Y = max(val.Y , val.X + lz[id].Y);
}

void update(int ql , int qr , int val , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		apply(id , pll(val , 0));
		return;
	}
	int mid = l + r >> 1;
	apply(lc , lz[id]); apply(rc , lz[id]); lz[id] = {0 , 0};
	update(ql , qr , val , lc , l , mid);
	update(ql , qr , val , rc , mid , r);
	mn[id] = min(mn[lc] , mn[rc]);
}

ll getVal(int x , int id = 1 , int l = 0 , int r = n){
	if(r - l == 1)	return mn[id];
	int mid = l + r >> 1;
	apply(lc , lz[id]); apply(rc , lz[id]); lz[id] = {0 , 0};
	if(x < mid)	return getVal(x , lc , l , mid);
	return getVal(x , rc , mid , r);
}

void insert(int x , pll y , int id = 1 , int l = 0 , int r = n){
	if(r - l == 1){
		vec[id].push_back(y);
		return;
	}
	int mid = l + r >> 1;
	if(x < mid)	insert(x , y , lc , l , mid);
	else	insert(x , y , rc , mid , r);
}

void build(int id = 1 , int l = 0 , int r = n){
	if(r - l == 1){
		sort(all(vec[id]) , greater<pll>());
		if(SZ(vec[id]) == 0)	seg[id] = INF;
		else	seg[id] = vec[id].back().X;
		return;
	}
	int mid = l + r >> 1;
	build(lc , l , mid);
	build(rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

void shift(int id){
	lz2[lc] += lz2[id]; seg[lc] -= lz2[id];
	lz2[rc] += lz2[id]; seg[rc] -= lz2[id];
	lz2[id] = 0;
}

void solve(int ql , int qr , int val , int col , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr && seg[id] > val){
		lz2[id] += val;
		seg[id] -= val;
		return;
	}
	if(r - l == 1){
		lz2[id] += val;
		seg[id] -= val;
		while(seg[id] <= 0){
			if(SZ(vec[id]) > 1){
				seg[id] += vec[id][SZ(vec[id]) - 2].X - vec[id].back().X;
			}
			else	seg[id] = INF;
			ans[vec[id].back().Y] = col;
			vec[id].pop_back();
		}
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	solve(ql , qr , val , col , lc , l , mid);
	solve(ql , qr , val , col , rc,  mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> m >> q;
	for(int i = 1 ; i <= q ; i++){
		ll type , l , r = -1 , val;
		cin >> type;
		if(type == 1){
			cin >> l >> r >> col[i] >> val; l--;
			add(l , val);
			add(r , -val);
			update(l , r , val);
		}
		if(type == 2){
			cin >> l >> r >> val; l--;
			update(l , r , -val);
		}
		if(type == 3){
			cin >> l >> val; l--;
			ll res = get(l) - getVal(l) + val;
			ans[i] = -1;
			if(res > get(l)){
				Q.push_back({type , l , r , val});
				continue;
			}
			insert(l , {res , i});
		}
		Q.push_back({type , l , r , val});
	}
	build();
	for(int i = 1 ; i <= q ; i++){
//		cout << i << sep << col[i] << endl;
		ll type = Q[i].type , l = Q[i].l , r = Q[i].r , val = Q[i].val;
		if(type == 1){
//			cout << i << endl;
			solve(l , r , val , col[i]);
		}
	}
	for(int i = 1 ; i <= q ; i++){
		//cout << i << sep << ans[i] << endl;
		if(ans[i] == 0)	continue;
		cout << max(ans[i] , 0ll) << endl;
	}

    return 0;
}
/*

*/

Compilation message (stderr)

foodcourt.cpp: In function 'void update(int, int, int, int, int, int)':
foodcourt.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid = l + r >> 1;
      |            ~~^~~
foodcourt.cpp: In function 'll getVal(int, int, int, int)':
foodcourt.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1;
      |            ~~^~~
foodcourt.cpp: In function 'void insert(int, pll, int, int, int)':
foodcourt.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |  int mid = l + r >> 1;
      |            ~~^~~
foodcourt.cpp: In function 'void build(int, int, int)':
foodcourt.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |  int mid = l + r >> 1;
      |            ~~^~~
foodcourt.cpp: In function 'void solve(int, int, int, int, int, int, int)':
foodcourt.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |  int mid = l + r >> 1;
      |            ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:148:18: warning: narrowing conversion of 'type' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  148 |     Q.push_back({type , l , r , val});
      |                  ^~~~
foodcourt.cpp:148:25: warning: narrowing conversion of 'l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  148 |     Q.push_back({type , l , r , val});
      |                         ^
foodcourt.cpp:148:29: warning: narrowing conversion of 'r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  148 |     Q.push_back({type , l , r , val});
      |                             ^
foodcourt.cpp:153:16: warning: narrowing conversion of 'type' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  153 |   Q.push_back({type , l , r , val});
      |                ^~~~
foodcourt.cpp:153:23: warning: narrowing conversion of 'l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  153 |   Q.push_back({type , l , r , val});
      |                       ^
foodcourt.cpp:153:27: warning: narrowing conversion of 'r' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  153 |   Q.push_back({type , l , r , val});
      |                           ^

• 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