oj.uz

답안 #922448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922448 2024-02-05T14:07:02 Z Onur_Ilgaz Meteors (POI11_met) C++17
100 / 100
 781 ms 48468 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 300005;
vector <int> station[N];
int from[N], to[N], add[N], need[N], ans[N];
int point;

struct BIT {
	int n;
	vector <int> t;
	void init(int size) {
		n = size;
		t.assign((n + 1) * 2, 0);
	}
	void update(int till, int val) {
		while(till) {
			t[till] += val;
			till = till - (till & (-till));
		}
	}
	int query(int ind) {
		int res = 0;
		while(ind <= n) {
			res += t[ind];
			ind = ind + (ind & (-ind));
		}
		return res;
	}
}t;

void f(int l, int r, vector<int>&owner) {
	if(owner.empty()) return;
	if(l == r) {
		for(auto it:owner) {
			ans[it] = l;
		}
		return;
	}
	int m = (l + r) / 2;
	int ul, ur, val;
	auto upd = [&]() {
		t.update(ul-1, -val);
		t.update(ur, val);
		if(ur < ul) {
			t.update(t.n, val);
		}
	};
	while(point < m) {
		point++;
		ul = from[point], ur = to[point], val = add[point];
		upd();
	}
	while(point > m) {
		ul = from[point], ur = to[point], val = -add[point];
		upd();
		point--;
	}
	// now point is at m
	vector <int> left, right;
	for(int it : owner) {
		int sum = 0;
		for(int itt : station[it]) {
			sum += t.query(itt);
			if(sum >= need[it]) break;
		}
		if(sum >= need[it]) 
			left.push_back(it);
		else 
			right.push_back(it);
	}
	owner.clear();
	f(l, m, left);
	f(m + 1, r, right);
}

int32_t main() {
	fast
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int in;
		cin >> in;
		station[in].push_back(i+1);
	}
	for(int i = 1; i <= n; i++) {
		cin >> need[i];
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> from[i] >> to[i] >> add[i];
	}
	vector <int> owner(n);
	for(int i = 0; i < n; i++) owner[i] = i+1;
	from[q+1] = 1, to[q+1] = m, add[q+1] = 0;
	t.init(m);
	f(1, q + 1, owner);
	for(int i = 1; i <= n; i++) {
		if(ans[i] > q) cout << "NIE\n";
		else cout << ans[i] << "\n";
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 20024 KB Output is correct
2 Correct 48 ms 25352 KB Output is correct
3 Correct 49 ms 20052 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 19804 KB Output is correct
2 Correct 46 ms 19968 KB Output is correct
3 Correct 40 ms 24192 KB Output is correct
4 Correct 21 ms 20052 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 19540 KB Output is correct
2 Correct 39 ms 24360 KB Output is correct
3 Correct 17 ms 17752 KB Output is correct
4 Correct 48 ms 20400 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 19320 KB Output is correct
2 Correct 42 ms 20032 KB Output is correct
3 Correct 30 ms 19560 KB Output is correct
4 Correct 56 ms 23612 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 46144 KB Output is correct
2 Correct 94 ms 30404 KB Output is correct
3 Correct 61 ms 19396 KB Output is correct
4 Correct 734 ms 43892 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 42972 KB Output is correct
2 Correct 86 ms 29468 KB Output is correct
3 Correct 42 ms 20304 KB Output is correct
4 Correct 781 ms 48468 KB Output is correct