oj.uz

답안 #381216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381216 2021-03-24T18:56:15 Z aryan12 Meteors (POI11_met) C++17
74 / 100
 640 ms 47116 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int64_t> req;
vector<vector<int64_t>> land;
vector<array<int64_t, 3>> D;
vector<int64_t> ans;
 
int64_t n, m;
 
struct BIT{
	vector<int64_t> tree;
	int64_t n;
 
	void init(int64_t _n){
		n = _n;
		tree.resize(n+1);
	}
 
	void upd(int64_t idx, int64_t val){
		for(; idx <= n; idx += (idx&(-idx)))
			tree[idx] += val;
	}
 
	void upd(int64_t l, int64_t r, int64_t val){
		upd(l, val);
		upd(r+1, -val);
	}
 
	int64_t query(int64_t idx){
		int64_t sum = 0;
		for(; idx > 0; idx -= (idx&(-idx)))
			sum += tree[idx];
		return sum;
	}
 
}bit;
 
void PBS(int64_t l, int64_t r, vector<int64_t> active){
	if(active.size() == 0)
		return;
 
	if(r - l == 1){
		for(int64_t i : active)
			ans[i] = l;
		return;
	}
 
	int64_t mid = (l + r) >> 1;
	
	for(int64_t i = l; i < mid; i++){
		if(D[i][0] <= D[i][1]) bit.upd(D[i][0], D[i][1], int64_t(D[i][2]));
		else{
			bit.upd(D[i][0], m, int64_t(D[i][2]));
			bit.upd(1, D[i][1], int64_t(D[i][2]));
		}
	}
	
	vector<int64_t> nq[2];
	
	for(int64_t i : active){
		int64_t sum = 0;
		for(int64_t v : land[i]) sum += bit.query(v);
		if(sum >= req[i]) nq[0].push_back(i);
		else{
			req[i] -= sum;
			nq[1].push_back(i);
		}
	}
 
	for(int64_t i = l; i < mid; i++){
		if(D[i][0] <= D[i][1]) bit.upd(D[i][0], D[i][1], int64_t(-D[i][2]));
		else{
			bit.upd(D[i][0], m, int64_t(-D[i][2]));
			bit.upd(1, D[i][1], int64_t(-D[i][2]));
		}
	}
 
	PBS(l, mid, nq[0]);
	PBS(mid, r, nq[1]);
}
 
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
 
	cin >> n >> m;
	land.resize(n+1), req.resize(n+1);
	ans.resize(n+1);
 
	bit.init(m);
 
	for(int64_t i = 1; i <= m; i++){
		int64_t x;
		cin >> x;
		land[x].push_back(i);
	}
 
	for(int64_t i = 1; i <= n; i++)
		cin >> req[i];
 
	int64_t k;
	cin >> k;
 
	D.resize(k+1);
	for(int64_t i = 1; i <= k; i++){
		auto& [l, r, upd] = D[i];
		cin >> l >> r >> upd;
	}
 
	vector<int64_t> cur(n);
	iota(cur.begin(), cur.end(), 1);
	PBS(1, k+2, cur);
 
	for(int64_t i = 1; i <= n; i++)
		if(ans[i] == k+1) cout << "NIE\n";
		else cout << ans[i] << '\n';
 
	return 0; 
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 4972 KB Output is correct
2 Correct 84 ms 11940 KB Output is correct
3 Correct 89 ms 5104 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 4716 KB Output is correct
2 Correct 89 ms 4716 KB Output is correct
3 Correct 74 ms 9052 KB Output is correct
4 Correct 31 ms 4988 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 4204 KB Output is correct
2 Correct 83 ms 9832 KB Output is correct
3 Correct 23 ms 2156 KB Output is correct
4 Correct 90 ms 5740 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3432 KB Output is correct
2 Correct 89 ms 4840 KB Output is correct
3 Correct 55 ms 3820 KB Output is correct
4 Correct 108 ms 7660 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 47116 KB Output is correct
2 Incorrect 289 ms 20212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 40288 KB Output is correct
2 Incorrect 289 ms 18544 KB Output isn't correct
3 Halted 0 ms 0 KB -