oj.uz

Submission #735520

# Submission time Handle Problem Language Result Execution time Memory
735520 2023-05-04T09:35:05 Z QwertyPi Food Court (JOI21_foodcourt) C++14
21 / 100
 616 ms 77908 KB 
#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;

struct np{
	int x = 0, y = 0;
	np() {};
	np(int v){
		if(v >= 0) x = 0, y = v;
		else x = -v, y = 0;
	}
	np(int x, int y) : x(x), y(y){
	}
	friend np operator+ (const np& a, const np& b) {
		return {a.x + b.x - min(a.y, b.x), a.y + b.y - min(a.y, b.x)};
	}
};

struct node{
	np acc;
	int sum = 0, psum = 0, nsum = 0, colour = 0;
	friend void add(node& res, const node& L, const node& R){
		res.acc = L.acc + R.acc;
		res.sum = L.sum + R.sum;
		res.psum = L.psum + R.psum;
		res.nsum = L.nsum + R.nsum;
	}
};

const int N_MAX = 2.5e5 + 11;

node t[N_MAX << 2];

void assign(int idx, int k, int c = 0, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr){
		t[v].acc = np(k);
		t[v].sum = k;
		t[v].nsum = k < 0 ? k : 0;
		t[v].psum = k > 0 ? k : 0;
		t[v].colour = c;
		return;
	}
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		assign(idx, k, c, v * 2 + 1, tl, tm);
	}else{
		assign(idx, k, c, v * 2 + 2, tm + 1, tr);
	}
	add(t[v], t[v * 2 + 1], t[v * 2 + 2]);
}

int bs(int k, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return tl;
	int tm = (tl + tr) / 2;
	if(t[v * 2 + 1].psum >= k){
		return bs(k, v * 2 + 1, tl, tm);
	}else{
		return bs(k - t[v * 2 + 1].psum, v * 2 + 2, tm + 1, tr);
	}
}

int psum(int r, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return t[v].psum;
	int tm = (tl + tr) / 2;
	if(r <= tm){
		return psum(r, v * 2 + 1, tl, tm);
	}else{
		return t[v * 2 + 1].psum + psum(r, v * 2 + 2, tm + 1, tr);
	}
}

np qry(int r, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return t[v].acc;
	int tm = (tl + tr) / 2;
	if(r <= tm){
		return qry(r, v * 2 + 1, tl, tm);
	}else{
		return t[v * 2 + 1].acc + qry(r, v * 2 + 2, tm + 1, tr);
	}
}

struct query{
	int p, i, t, c, k;
};

vector<query> Q;
int C[N_MAX];

int32_t main(){
	cin.tie(0);
	cout.tie(0)->sync_with_stdio(false);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < q; i++){
		int l, r, a, c, k;
		int t; cin >> t;
		switch(t){
			case 1: t = 1; cin >> l >> r >> c >> k; Q.push_back({l, i, 1, c, k}); Q.push_back({r + 1, i, 1, c, 0}); break;
			case 2: t = 2; cin >> l >> r >> k; Q.push_back({l, i, 1, 0, -k}); Q.push_back({r + 1, i, 1, 0, 0}); break;
			case 3: t = 3; cin >> a >> k; Q.push_back({a, i, 2, 0, k}); break;
		}
		C[i] = Q.back().c; 
	}
	sort(Q.begin(), Q.end(), [](query a, query b){
		return a.p < b.p || a.p == b.p && a.i < b.i;
	});
	map<int, int> ans;
	for(auto& q : Q){
		if(q.t == 1) assign(q.i, q.k, q.c);
		else {
			auto acc = qry(q.i);
			if(acc.y < q.k){
				ans[q.i] = 0;
			}else{
				ans[q.i] = 1;
			}
		}
	}
	for(auto [i, j] : ans){
		cout << j << endl;
	}
}

Compilation message

foodcourt.cpp: In lambda function:
foodcourt.cpp:105:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  105 |   return a.p < b.p || a.p == b.p && a.i < b.i;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:119:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |  for(auto [i, j] : ans){
      |           ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 54624 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 518 ms 71584 KB Output is correct
2 Correct 402 ms 72892 KB Output is correct
3 Correct 555 ms 76848 KB Output is correct
4 Correct 371 ms 73044 KB Output is correct
5 Correct 355 ms 72852 KB Output is correct
6 Correct 485 ms 76576 KB Output is correct
7 Correct 326 ms 75108 KB Output is correct
8 Correct 350 ms 75048 KB Output is correct
9 Correct 561 ms 77908 KB Output is correct
10 Correct 566 ms 77908 KB Output is correct
11 Correct 476 ms 76456 KB Output is correct
12 Correct 495 ms 76460 KB Output is correct
13 Correct 512 ms 76556 KB Output is correct
14 Correct 479 ms 76444 KB Output is correct
15 Correct 506 ms 76468 KB Output is correct
16 Correct 500 ms 76444 KB Output is correct
17 Correct 526 ms 76364 KB Output is correct
18 Correct 575 ms 76532 KB Output is correct
19 Correct 616 ms 76428 KB Output is correct
20 Correct 509 ms 76424 KB Output is correct
21 Correct 495 ms 76552 KB Output is correct
22 Correct 524 ms 76396 KB Output is correct
23 Correct 570 ms 76392 KB Output is correct
24 Correct 513 ms 76504 KB Output is correct
25 Correct 482 ms 76132 KB Output is correct
26 Correct 493 ms 76756 KB Output is correct
27 Correct 376 ms 75656 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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