oj.uz

Submission #656468

# Submission time Handle Problem Language Result Execution time Memory
656468 2022-11-07T14:51:41 Z PoPularPlusPlus Food Court (JOI21_foodcourt) C++17
21 / 100
 271 ms 19064 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

struct item {
	ll a , b;
};

struct Seg {
	vector<item> v;
	vector<ll> arr;
	int siz;
	
	item nutral = {0,0};
	
	item merge(item x , item y){
		ll a = min(x.b , y.a);
		y.a -= a;
		x.b -= a;
		x.a += y.a;
		x.b += y.b;
		return x;
	}
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		
		v.assign(siz * 2 , nutral);
		arr.assign(siz * 2 , 0);
	}
	
	ll find(int i , int x , int lx , int rx){
		if(rx - lx == 1){
			arr[x] -= v[x].a;
			arr[x] = max(arr[x] , 0LL);
			arr[x] += v[x].b;
			v[x] = nutral;
			return arr[x];
		}
		int m = (lx + rx)/2;
		v[2 * x + 1] = merge(v[2 * x + 1] , v[x]);
		v[2 * x + 2] = merge(v[2 * x + 2] , v[x]);
		v[x] = nutral;
		if(i < m){
			return find(i , 2 * x + 1 , lx , m);
		}
		else return find(i , 2 * x + 2 , m , rx);
	}
	
	ll find(int i){
		return find(i , 0 , 0 , siz);
	}
	
	void range(int l , int r , item it , int x , int lx , int rx){
		if(l >= rx || r <= lx)return;
		if(lx >= l && rx <= r){
			v[x] = merge(v[x] , it);
			return;
		}
		v[2 * x + 1] = merge(v[2 * x + 1] , v[x]);
		v[2 * x + 2] = merge(v[2 * x + 2] , v[x]);
		v[x] = nutral;
		int m = (lx + rx)/2;
		range(l , r , it , 2 * x + 1 , lx , m);
		range(l , r , it , 2 * x + 2 , m , rx);
	}
	
	void range(int l , int r , item it){
		range(l , r , it , 0 , 0 , siz);
	}
};

void solve(){
	int n , m , q;
	cin >> n >> m >> q;
	Seg st;
	st.init(n);
	item it;
	while(q--){
		int ti;
		cin >> ti;
		if(ti == 1){
			int l , r, c , k;
			cin >> l >> r >> c >> k;
			it.a = 0;
			it.b = k;
			st.range(l-1 , r , it);
		}
		else if(ti == 2){
			int l , r , k;
			cin >> l >> r >> k;
			it.a = k;
			it.b = 0;
			st.range(l -1 , r , it);
		}
		else {
			ll a , b;
			cin >> a >> b;
			ll x = st.find(a-1);
			if(x >= b)cout << 1 << '\n';
			else cout << 0 << '\n';
		}
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 12764 KB Output is correct
2 Correct 200 ms 16920 KB Output is correct
3 Correct 232 ms 18684 KB Output is correct
4 Correct 183 ms 17116 KB Output is correct
5 Correct 204 ms 17252 KB Output is correct
6 Correct 235 ms 18892 KB Output is correct
7 Correct 72 ms 4560 KB Output is correct
8 Correct 76 ms 4424 KB Output is correct
9 Correct 236 ms 19064 KB Output is correct
10 Correct 209 ms 18892 KB Output is correct
11 Correct 253 ms 18780 KB Output is correct
12 Correct 229 ms 18916 KB Output is correct
13 Correct 231 ms 18844 KB Output is correct
14 Correct 245 ms 18752 KB Output is correct
15 Correct 262 ms 18780 KB Output is correct
16 Correct 237 ms 18744 KB Output is correct
17 Correct 271 ms 18668 KB Output is correct
18 Correct 231 ms 18764 KB Output is correct
19 Correct 238 ms 18788 KB Output is correct
20 Correct 230 ms 18780 KB Output is correct
21 Correct 264 ms 18772 KB Output is correct
22 Correct 248 ms 18800 KB Output is correct
23 Correct 236 ms 18764 KB Output is correct
24 Correct 259 ms 18636 KB Output is correct
25 Correct 200 ms 18272 KB Output is correct
26 Correct 206 ms 18396 KB Output is correct
27 Correct 203 ms 18508 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -