oj.uz

답안 #396155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396155 2021-04-29T13:55:59 Z oolimry 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 1000 ms 12152 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

const lint inf = 1234567890123456;
int n, M, Q;

struct thing{ lint v, l, r; };
inline thing merge(thing a, thing b){
	if(a.v == b.v and a.r == b.l - 1) return {a.v, a.l, b.r};
	else if(a.v > b.v) return b;
	else return a;
}
const int B = 18;
const int N = 1 << B;
struct seg{
	thing tree[2*N];
	lint lazy[2*N];
	
	inline int l(int u){ return (u<<1); }
	inline int r(int u){ return (u<<1|1); }
	seg(){
		fill(lazy,lazy+2*N,0);
		for(int i = 0;i < N;i++) tree[i+N] = {0,i,i};
		for(int i = N-1;i;i >>= 1) tree[i] = merge(tree[i], tree[r(i)]);
	}

	inline void apply(int u, lint L){
		tree[u].v += L;
		lazy[u] += L;
	}
	inline void push(int leaf){
		leaf += N;
		int u = 0;
		for(int i = B;i >= 1;i--){
			u <<= 1;
			if(leaf & (1<<i)) u |= 1;
			
			apply(l(u), lazy[u]);
			apply(r(u), lazy[u]);
			lazy[u] = 0;
		}
	}
	inline void pull(int u){
		u += N;
		for(int i = 0;i < B;i++){
			u >>= 1;
			tree[u] = merge(tree[l(u)], tree[r(u)]);
		}
	}

	void update(int l, int r, lint L){
		int ll = l, rr = r;
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1) apply(l++, L);
			if(r&1) apply(--r, L);
		}
		push(ll), push(rr);
		pull(ll); pull(rr);
	}
	 
	thing query(int l, int r){
		push(l), push(r);
		thing L = {inf,0,0}, R = {inf,0,0};
		
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1){
				L = merge(L, tree[l++]);
			}
			if(r&1){
				R = merge(tree[--r], R);
			}
		}
		
		return merge(L,R);
	}
	
} *root;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> M >> Q;
	
	root = new seg();
	
	for(int i = 0;i < Q;i++){
		int t; cin >> t;
		if(t == 1){
			int l, r, c, k; cin >> l >> r >> c >> k;
			root->update(l,r,k);
		}
		else if(t == 2){ 
			int l, r, k; cin >> l >> r >> k;
			root->update(l,r,-k);
			
			while(true){
				thing small = root->query(1,n);
				//show(small.v);
				if(small.v >= 0) break;
				root->update(small.l, small.r, -small.v);
				//show2(small.l, small.r);
			}
		}
		else{
			lint a, b; cin >> a >> b;
			thing res = root->query(a,a);
			if(res.v >= b) cout << "1\n";
			else cout << "0\n";
		}
		
		//for(int i = 1;i <= n;i++) cerr << root->query(i,i).v << " "; cerr << endl;
	}
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1097 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -