oj.uz

답안 #735354

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

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

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] = node(k, 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);
	}
	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:83:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   83 |   return a.p < b.p || a.p == b.p && a.i < b.i;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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