답안 #1034890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034890	2024-07-25T20:47:38 Z	xnqs	Meteors (POI11_met)	C++17	74 / 100	3524 ms	65536 KB

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
 
struct Operation {
	int64_t l, r, amt;
	Operation():
		l(0), r(0), amt(0) {}
	Operation(int64_t l, int64_t r, int64_t amt):
		l(l), r(r), amt(amt) {}
};
 
struct ParallelBSQuery {
	int64_t color;
	int64_t l, r, m;
	ParallelBSQuery():
		color(0), l(0), r(0), m(0) {}
	ParallelBSQuery(int64_t color, int64_t l, int64_t r):
		color(color), l(l), r(r), m((l+r)>>1) {}
};
 
int64_t x, q, ops;
int64_t color[310005];
int64_t target[310005];
int64_t ans[310005];
int64_t tree[1250005];
int64_t lazy[1250005];
std::vector<Operation> operations;
std::vector<ParallelBSQuery> queries;
std::vector<int64_t> owned_by[600005];
 
void push(int64_t node, int64_t l, int64_t r) {
	tree[node] += lazy[node];
	if (l!=r) {
		lazy[node<<1] += lazy[node];
		lazy[node<<1|1] += lazy[node];
	}
	lazy[node] = 0;
}
 
void update(int64_t node, int64_t l, int64_t r, int64_t st, int64_t fi, int64_t val) {
	push(node,l,r);
	if (l>fi||r<st) {
		return;
	}
	if (st<=l&&r<=fi) {
		lazy[node] += val;
		push(node,l,r);
		return;
	}
 
	int64_t m = (l+r)>>1;
	update(node<<1,l,m,st,fi,val);
	update(node<<1|1,m+1,r,st,fi,val);
	tree[node] = tree[node<<1] + tree[node<<1|1];
}
 
int64_t query(int64_t node, int64_t l, int64_t r, int64_t st, int64_t fi) {
	push(node,l,r);
	if (l>fi||r<st) {
		return 0;
	}
	if (st<=l&&r<=fi) {
		return tree[node];
	}
 
	int64_t m = (l+r)>>1;
	return query(node<<1,l,m,st,fi) + query(node<<1|1,m+1,r,st,fi);
}
 
int64_t get_sum(int64_t color) {
	int64_t ret = 0;
	for (const auto& i : owned_by[color]) {
		ret += query(1,1,x,i,i);
	}
	return ret;
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> q >> x;
	for (int64_t i = 1; i <= x; i++) {
		std::cin >> color[i];
		owned_by[color[i]].emplace_back(i);
	}
 
	for (int64_t i = 1; i <= q; i++) {
		std::cin >> target[i];
	}
 
	std::cin >> ops;
	operations.reserve(ops);
	for (int64_t i = 0, l, r, amt; i < ops; i++) {
		std::cin >> l >> r >> amt;
		operations.emplace_back(l,r,amt);
	}
 
	for (int64_t i = 0; i < q; i++) {
		ans[i+1] = -1;
		queries.emplace_back(i+1,0,ops-1);
	}
 
	for (int64_t iterations = 0; iterations < 19; iterations++) {
		memset(tree,0,sizeof(tree));
		memset(lazy,0,sizeof(lazy));
		std::sort(queries.begin(),queries.end(),[](const ParallelBSQuery& a, const ParallelBSQuery& b) {
			return a.m < b.m;
		});
 
		int64_t scanline = 0;
		for (auto& [color, l, r, m] : queries) {
			if (l>r) {
				continue;
			}
 
			while (scanline<=m) {
				auto [i, j, amt] = operations[scanline];
				if (i>j) {
					update(1,1,x,1,j,amt);
					update(1,1,x,i,x,amt);
				}
				else {
					update(1,1,x,i,j,amt);
				}
				++scanline;
			}
 
			int64_t cand = get_sum(color);
			if (cand>=target[color]) {
				ans[color] = m;
				r = m-1;
			}
			else {
				l = m+1;
			}
 
			m = (l+r)>>1;
		}
	}
 
	for (int64_t i = 1; i <= q; i++) {
		if (ans[i]==-1) std::cout << "NIE\n";
		else std::cout << ans[i]+1 << "\n";
	}
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	38292 KB	Output is correct
2	Correct	16 ms	39512 KB	Output is correct
3	Correct	23 ms	39516 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	39516 KB	Output is correct
2	Correct	17 ms	39516 KB	Output is correct
3	Correct	26 ms	39736 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	411 ms	41676 KB	Output is correct
2	Correct	523 ms	42448 KB	Output is correct
3	Correct	477 ms	42112 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	473 ms	41692 KB	Output is correct
2	Correct	503 ms	41928 KB	Output is correct
3	Correct	456 ms	42444 KB	Output is correct
4	Correct	143 ms	41100 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	246 ms	41688 KB	Output is correct
2	Correct	403 ms	42456 KB	Output is correct
3	Correct	77 ms	40728 KB	Output is correct
4	Correct	418 ms	42196 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	203 ms	41332 KB	Output is correct
2	Correct	363 ms	41960 KB	Output is correct
3	Correct	372 ms	41512 KB	Output is correct
4	Correct	409 ms	42700 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3524 ms	65536 KB	Output is correct
2	Incorrect	2697 ms	58644 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3391 ms	64860 KB	Output is correct
2	Incorrect	1368 ms	57192 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

답안 #1034890

Compilation message