oj.uz

답안 #682353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682353 2023-01-16T07:01:52 Z vjudge1 푸드 코트 (JOI21_foodcourt) C++17
7 / 100
 297 ms 86636 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using ordered_multiset =tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update> ;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define ft first
#define sd second
#define ll long long
#define pll pair<ll,ll>
const int N = 3e5 + 5;
const int M = 1e7 + 5;
const ll mod = 998244353;
const ll inf = 1e18;
 
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res=binmul(res,x);x=binmul(x,x);ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }
 
ll n, m, q, ind[2001], sz[2001], t[N * 4], fl[N * 4][3];
set<pll> st[2001];
 
void push(ll x, ll v, ll tl, ll tr) {
	if (tl == tr) {
		t[v] -= fl[v][2];
		t[v] = max(t[v], 0ll);
		if (x == 1) {
			t[v] += fl[v][1];
		}
	} else {
		if (x == 1) {
			fl[v + v][1] -= fl[v + v][2];
			fl[v + v][1] = max(0ll, fl[v + v][1]);
			
			fl[v + v + 1][1] -= fl[v + v + 1][2];
			fl[v + v + 1][1] = max(0ll, fl[v + v + 1][1]);

			fl[v + v][2] = fl[v + v + 1][2] = 0;
		} else {
			fl[v + v][1] += fl[v][1];
			fl[v + v + 1][1] += fl[v][1];
	
			fl[v + v][2] += fl[v][2];
			fl[v + v + 1][2] += fl[v][2];
		}
	}
	fl[v][1] = fl[v][2] = 0;
}
 
void upd(ll x, ll l, ll r, ll k, ll v = 1, ll tl = 1, ll tr = n) {
	push(x, v, tl, tr);
	if (r < tl || tr < l) return;
	if (l <= tl && tr <= r) {
		if (x == 1) {
			fl[v][1] -= fl[v][2];
			fl[v][2] = 0;
			fl[v][1] = max(0ll, fl[v][1]);
		}
		fl[v][x] += k;
		push(x, v, tl, tr);
		return;
	}
	ll tm = (tl + tr) / 2;
	upd(x, l, r, k, v + v, tl, tm);
	upd(x, l, r, k, v + v + 1, tm + 1, tr);
}
 
ll get(ll pos, ll v = 1, ll tl = 1, ll tr = n) {
	push(1, v, tl, tr);
	if (tl == tr) return t[v];
	ll tm = (tl + tr) / 2;
	if (pos <= tm) return get(pos, v + v, tl, tm);
	else return get(pos, v + v + 1, tm + 1, tr);
}
 
const void solve() {
	cin >> n >> m >> q;
 
	if (m == 1) {
		for (int i = 1; i <= q; ++ i) {
			ll t;
			cin >> t;
			if (t == 1) {
				ll l, r, c, k;
				cin >> l >> r >> c >> k;
				upd(1, l, r, k);	
			} else if (t == 2) {
				ll l, r, k;
				cin >> l >> r >> k;
				upd(2, l, r, k);
			} else {
				ll a, b;
				cin >> a >> b;
				if (get(a) >= b) cout << "1\n";
				else cout << "0\n";
			}
		}
		return;
	}
 
	for (int i = 1; i <= q; ++ i) {
		ll t;
		cin >> t;
		if (t == 1) {
			ll l, r, c, k;
			cin >> l >> r >> c >> k;
		    for (int j = l; j <= r; ++ j) {
		    	st[j].insert({sz[j] + k, c});
		    	sz[j] += k;
		    }
		} else if (t == 2) {
			ll l, r, k;
			cin >> l >> r >> k;
		    for (int j = l; j <= r; ++ j) {
		    	ind[j] += k;
		    	ind[j] = min(ind[j], sz[j]);
		    }
		} else {
			ll a, b;
			cin >> a >> b;
			auto it = st[a].lower_bound({ind[a] + b, 0ll});
			if (it == st[a].end()) cout << "0\n";
			else cout << it->sd << "\n";
		}
	}
}
 
int main() {
   	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	srand(time(NULL));
 
	ll tt = 1;
	//cin >> tt; 
 
	while (tt --) solve();
 
	return 0;
}

Compilation message

foodcourt.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("O3")
      | 
foodcourt.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization("unroll-loops")
      | 
foodcourt.cpp:7: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    7 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 16076 KB Output is correct
2 Correct 69 ms 28564 KB Output is correct
3 Correct 106 ms 40312 KB Output is correct
4 Correct 188 ms 63000 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 123 ms 48432 KB Output is correct
8 Correct 128 ms 48160 KB Output is correct
9 Correct 125 ms 47796 KB Output is correct
10 Correct 127 ms 48336 KB Output is correct
11 Correct 138 ms 49596 KB Output is correct
12 Correct 130 ms 48632 KB Output is correct
13 Correct 96 ms 60492 KB Output is correct
14 Correct 206 ms 86636 KB Output is correct
15 Correct 118 ms 59692 KB Output is correct
16 Correct 163 ms 85088 KB Output is correct
17 Correct 62 ms 23896 KB Output is correct
18 Correct 108 ms 41500 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 3 ms 1072 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 16076 KB Output is correct
2 Correct 69 ms 28564 KB Output is correct
3 Correct 106 ms 40312 KB Output is correct
4 Correct 188 ms 63000 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 123 ms 48432 KB Output is correct
8 Correct 128 ms 48160 KB Output is correct
9 Correct 125 ms 47796 KB Output is correct
10 Correct 127 ms 48336 KB Output is correct
11 Correct 138 ms 49596 KB Output is correct
12 Correct 130 ms 48632 KB Output is correct
13 Correct 96 ms 60492 KB Output is correct
14 Correct 206 ms 86636 KB Output is correct
15 Correct 118 ms 59692 KB Output is correct
16 Correct 163 ms 85088 KB Output is correct
17 Correct 62 ms 23896 KB Output is correct
18 Correct 108 ms 41500 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 3 ms 1072 KB Output is correct
21 Correct 70 ms 25420 KB Output is correct
22 Correct 64 ms 28352 KB Output is correct
23 Correct 127 ms 40556 KB Output is correct
24 Correct 203 ms 62372 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 175 ms 46488 KB Output is correct
28 Correct 138 ms 49572 KB Output is correct
29 Correct 137 ms 47436 KB Output is correct
30 Correct 138 ms 48540 KB Output is correct
31 Correct 136 ms 45696 KB Output is correct
32 Correct 129 ms 44796 KB Output is correct
33 Correct 137 ms 61136 KB Output is correct
34 Correct 211 ms 85392 KB Output is correct
35 Correct 101 ms 59596 KB Output is correct
36 Correct 173 ms 83888 KB Output is correct
37 Correct 2 ms 852 KB Output is correct
38 Correct 3 ms 1108 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 696 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 16076 KB Output is correct
2 Correct 69 ms 28564 KB Output is correct
3 Correct 106 ms 40312 KB Output is correct
4 Correct 188 ms 63000 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 123 ms 48432 KB Output is correct
8 Correct 128 ms 48160 KB Output is correct
9 Correct 125 ms 47796 KB Output is correct
10 Correct 127 ms 48336 KB Output is correct
11 Correct 138 ms 49596 KB Output is correct
12 Correct 130 ms 48632 KB Output is correct
13 Correct 96 ms 60492 KB Output is correct
14 Correct 206 ms 86636 KB Output is correct
15 Correct 118 ms 59692 KB Output is correct
16 Correct 163 ms 85088 KB Output is correct
17 Correct 62 ms 23896 KB Output is correct
18 Correct 108 ms 41500 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 3 ms 1072 KB Output is correct
21 Runtime error 2 ms 696 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 16076 KB Output is correct
2 Correct 69 ms 28564 KB Output is correct
3 Correct 106 ms 40312 KB Output is correct
4 Correct 188 ms 63000 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 123 ms 48432 KB Output is correct
8 Correct 128 ms 48160 KB Output is correct
9 Correct 125 ms 47796 KB Output is correct
10 Correct 127 ms 48336 KB Output is correct
11 Correct 138 ms 49596 KB Output is correct
12 Correct 130 ms 48632 KB Output is correct
13 Correct 96 ms 60492 KB Output is correct
14 Correct 206 ms 86636 KB Output is correct
15 Correct 118 ms 59692 KB Output is correct
16 Correct 163 ms 85088 KB Output is correct
17 Correct 62 ms 23896 KB Output is correct
18 Correct 108 ms 41500 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 3 ms 1072 KB Output is correct
21 Correct 70 ms 25420 KB Output is correct
22 Correct 64 ms 28352 KB Output is correct
23 Correct 127 ms 40556 KB Output is correct
24 Correct 203 ms 62372 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 175 ms 46488 KB Output is correct
28 Correct 138 ms 49572 KB Output is correct
29 Correct 137 ms 47436 KB Output is correct
30 Correct 138 ms 48540 KB Output is correct
31 Correct 136 ms 45696 KB Output is correct
32 Correct 129 ms 44796 KB Output is correct
33 Correct 137 ms 61136 KB Output is correct
34 Correct 211 ms 85392 KB Output is correct
35 Correct 101 ms 59596 KB Output is correct
36 Correct 173 ms 83888 KB Output is correct
37 Correct 2 ms 852 KB Output is correct
38 Correct 3 ms 1108 KB Output is correct
39 Runtime error 2 ms 696 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 16076 KB Output is correct
2 Correct 69 ms 28564 KB Output is correct
3 Correct 106 ms 40312 KB Output is correct
4 Correct 188 ms 63000 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 123 ms 48432 KB Output is correct
8 Correct 128 ms 48160 KB Output is correct
9 Correct 125 ms 47796 KB Output is correct
10 Correct 127 ms 48336 KB Output is correct
11 Correct 138 ms 49596 KB Output is correct
12 Correct 130 ms 48632 KB Output is correct
13 Correct 96 ms 60492 KB Output is correct
14 Correct 206 ms 86636 KB Output is correct
15 Correct 118 ms 59692 KB Output is correct
16 Correct 163 ms 85088 KB Output is correct
17 Correct 62 ms 23896 KB Output is correct
18 Correct 108 ms 41500 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 3 ms 1072 KB Output is correct
21 Correct 70 ms 25420 KB Output is correct
22 Correct 64 ms 28352 KB Output is correct
23 Correct 127 ms 40556 KB Output is correct
24 Correct 203 ms 62372 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 175 ms 46488 KB Output is correct
28 Correct 138 ms 49572 KB Output is correct
29 Correct 137 ms 47436 KB Output is correct
30 Correct 138 ms 48540 KB Output is correct
31 Correct 136 ms 45696 KB Output is correct
32 Correct 129 ms 44796 KB Output is correct
33 Correct 137 ms 61136 KB Output is correct
34 Correct 211 ms 85392 KB Output is correct
35 Correct 101 ms 59596 KB Output is correct
36 Correct 173 ms 83888 KB Output is correct
37 Correct 2 ms 852 KB Output is correct
38 Correct 3 ms 1108 KB Output is correct
39 Runtime error 2 ms 696 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -