oj.uz

답안 #680965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680965 2023-01-12T06:58:25 Z TranGiaHuy1508 Meteors (POI11_met) C++17
100 / 100
 3795 ms 63572 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

const int inf = 1e18;

struct Segtree{
	vector<int> tree;
	int _n;

	Segtree(int N): tree(4*N, 0), _n(N) {}

	void update(int tl, int tr, int delta) { update(1, 0, _n - 1, tl, tr, delta); }
	void update(int i, int l, int r, int tl, int tr, int delta){
		if (tl <= l && r <= tr) tree[i] += delta;
		else if (tl > r || tr < l) {}
		else{
			int mid = (l + r) >> 1;
			update(i<<1, l, mid, tl, tr, delta);
			update(i<<1|1, mid+1, r, tl, tr, delta);
		}
	}

	int get(int pos) { return get(1, 0, _n - 1, pos); }
	int get(int i, int l, int r, int pos){
		if (l == pos && r == pos) return tree[i];
		int mid = (l + r) >> 1;
		if (pos <= mid) return tree[i] + get(i<<1, l, mid, pos);
		else return tree[i] + get(i<<1|1, mid+1, r, pos);
	}
};

struct Query{
	int l, r, c;
};

struct ParallelBinarySearch{
	int l, r;
	vector<int> q;

	ParallelBinarySearch(int L, int R): l(L), r(R) {}
};

int N, M, Q;
vector<int> res, d;
vector<vector<int>> houses;
vector<Query> qs;

void main_program(){
	cin >> M >> N;

	res.assign(M, 0);
	d.resize(M);
	houses.resize(M);

	for (int i = 0; i < N; i++){
		int x; cin >> x; x--;
		houses[x].push_back(i);
	}

	for (int i = 0; i < M; i++){
		cin >> d[i];
	}

	cin >> Q;
	qs.resize(Q);

	for (int i = 0; i < Q; i++){
		int l, r, c; cin >> l >> r >> c; l--; r--;
		qs[i] = Query{l, r, c};
	}

	vector<ParallelBinarySearch> pbs;
	
	pbs.emplace_back(0, Q);
	pbs[0].q.resize(M);
	iota(pbs[0].q.begin(), pbs[0].q.end(), 0);

	while (!pbs.empty()){
		Segtree st(N);
		vector<ParallelBinarySearch> newpbs;
		int crr = -1;

		// DEBUG //
		// for (auto range: pbs){
		// 	cout << range.l << " -> " << range.r << ":";
		// 	for (auto i: range.q) cout << " " << i;
		// 	cout << "\n";
		// }
		// DEBUG //

		for (auto range: pbs){
			if (range.l == range.r){
				for (auto i: range.q) res[i] = range.l;
				continue;
			}

			int mid = (range.l + range.r) >> 1;
			ParallelBinarySearch leftnode(range.l, mid), rightnode(mid+1, range.r);

			while (crr < mid){
				crr++;
				int ql = qs[crr].l, qr = qs[crr].r, qc = qs[crr].c;

				if (ql <= qr) st.update(ql, qr, qc);
				else{
					st.update(ql, N-1, qc); st.update(0, qr, qc);
				}

				// DEBUG //
				// cout << "crr: " << crr << "\n";
				// for (int i = 0; i < N; i++) cout << st.get(i) << " \n"[i == N-1];
				// DEBUG //
			}

			for (auto i: range.q){
				int total = 0;
				for (auto j: houses[i]){
					total = min(inf, total + st.get(j));
				}
				if (total >= d[i]) leftnode.q.push_back(i);
				else rightnode.q.push_back(i);
			}

			if (!leftnode.q.empty()) newpbs.push_back(leftnode);
			if (!rightnode.q.empty()) newpbs.push_back(rightnode);
		}

		pbs.swap(newpbs);
	}

	for (int i = 0; i < M; i++){
		if (res[i] == Q) cout << "NIE\n";
		else cout << res[i] + 1 << "\n";
	}
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 4224 KB Output is correct
2 Correct 324 ms 6088 KB Output is correct
3 Correct 316 ms 6580 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 303 ms 5544 KB Output is correct
2 Correct 296 ms 5512 KB Output is correct
3 Correct 312 ms 6000 KB Output is correct
4 Correct 59 ms 4024 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 4784 KB Output is correct
2 Correct 204 ms 6748 KB Output is correct
3 Correct 56 ms 1572 KB Output is correct
4 Correct 303 ms 7000 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 3564 KB Output is correct
2 Correct 276 ms 5512 KB Output is correct
3 Correct 264 ms 4068 KB Output is correct
4 Correct 325 ms 7724 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3037 ms 30564 KB Output is correct
2 Correct 446 ms 19196 KB Output is correct
3 Correct 450 ms 6656 KB Output is correct
4 Correct 3795 ms 55764 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3009 ms 29560 KB Output is correct
2 Correct 769 ms 19204 KB Output is correct
3 Correct 76 ms 5324 KB Output is correct
4 Correct 3351 ms 63572 KB Output is correct