oj.uz

답안 #735355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735355 2023-05-04T03:43:41 Z QwertyPi 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 1000 ms 26800 KB 
#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;

struct node{
	int pmax = -INF, sum = 0, colour = 0;
	friend void add(node& res, const node& L, const node& R){
		res.pmax = max(L.pmax, L.sum + R.pmax);
		res.sum = L.sum + R.sum;
	}
};

const int N_MAX = 2.5e5 + 11;

node t[N_MAX << 2];

void add(int idx, int k, int c = 0, int v = 0, int tl = 0, int tr = N_MAX - 1){
	// if(v == 0) cout << "ADD " << idx << ' ' << k << ' ' << c << endl;
	if(tl == tr){
		t[v].pmax = t[v].sum = k;
		t[v].colour = c;
		return;
	}
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		add(idx, k, c, v * 2 + 1, tl, tm);
	}else{
		add(idx, k, c, v * 2 + 2, tm + 1, tr);
	}
	add(t[v], t[v * 2 + 1], t[v * 2 + 2]);
}

int qry(int idx, int k, int v = 0, int tl = 0, int tr = N_MAX - 1){
	// if(v == 0) cout << "QRY " << idx << ' ' << k << endl;
	if(tl == tr) return t[v].pmax >= k ? t[v].colour : 0;
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		return qry(idx, k, v * 2 + 1, tl, tm);
	}else{
		int q1 = qry(idx, k, v * 2 + 1, tl, tm);
		int q2 = qry(idx, k - t[v * 2 + 1].sum, v * 2 + 2, tm + 1, tr);
		// cout << q1 << ' ' << q2 << endl;
		return q2 ? q2 : q1;
	}
}


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

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

vector<query> Q;
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, 0, 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;
		}
	}
	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) add(q.i, q.k, q.c);
		else {
			ans[q.i] = sum(q.i) >= q.k ? 1 : 0;
		}
	}
	for(auto [i, j] : ans){
		cout << j << endl;
	}
}

Compilation message

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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