oj.uz

답안 #548547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548547 2022-04-13T18:33:59 Z 2fat2code Meteors (POI11_met) C++17
100 / 100
 1246 ms 42736 KB 
#include<bits/stdc++.h>
using namespace std;

const int pot = 512 * 1024;
long long tr[2*pot];

vector<int> properties[pot];
int need[pot];
int ans[pot];
int from[pot], to[pot], val[pot];

void tree_add(int low, int high, int v) {
	assert(low <= high);
	low += pot;
	high += pot;
	tr[low] += v;
	if(low != high) tr[high] += v;
	while(low + 1 < high) {
		if(low % 2 == 0) tr[low+1] += v;
		if(high % 2 == 1) tr[high-1] += v;
		low /= 2;
		high /= 2;
	}
}
void tree_add(int i_q, int multiplier) {
	int v = val[i_q] * multiplier;
	if(from[i_q] <= to[i_q])
		tree_add(from[i_q], to[i_q], v);
	else {
		tree_add(from[i_q], pot - 1, v);
		tree_add(0, to[i_q], v);
	}
}
long long tree_get(int where) {
	long long s = 0;
	for(int x = pot + where; x >= 1; x /= 2)
		s += tr[x];
	return s;
}

void rec(int low, int high, vector<int> & owners, int & act_tree) {
	if(owners.empty()) return;
	int mid = (low + high) / 2;
	while(act_tree < mid)
		tree_add(++act_tree, 1);
	while(act_tree > mid)
		tree_add(act_tree--, -1);
	
	vector<int> left_owners;
	vector<int> right_owners;
	for(int who : owners) {
		long long his_value = 0;
		for(int where : properties[who]) {
			his_value += tree_get(where);
			if(his_value >= need[who]) break;
		}
		if(his_value >= need[who]) {
			left_owners.push_back(who);
			ans[who] = high;
		}
		else
			right_owners.push_back(who);
	}
	owners.clear(); // thanks to this line the memory is O(n), not O(n log(n))
	if(low < high) {
		rec(low, mid, left_owners, act_tree);
		rec(mid + 1, high, right_owners, act_tree);
	}
}

int main() {
	int n, len;
	scanf("%d%d", &n, &len);
	for(int where = 1; where <= len; ++where) {
		int who;
		scanf("%d", &who);
		properties[who].push_back(where);
	}
	for(int who = 1; who <= n; ++who)
		scanf("%d", &need[who]);
	int q;
	scanf("%d", &q);
	for(int day = 1; day <= q; ++day)
		scanf("%d%d%d", &from[day], &to[day], &val[day]);
	
	vector<int> owners;
	for(int who = 1; who <= n; ++who)
		owners.push_back(who);
	
	int act_tree = 0;
	rec(1, q, owners, act_tree);
	
	for(int who = 1; who <= n; ++who) {
		if(ans[who]) printf("%d\n", ans[who]);
		else puts("NIE");
	}
	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d", &n, &len);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d", &who);
      |   ~~~~~^~~~~~~~~~~~
met.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d", &need[who]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
met.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d", &from[day], &to[day], &val[day]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12768 KB Output is correct
3 Correct 8 ms 12628 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 8 ms 12656 KB Output is correct
3 Correct 7 ms 12692 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 14744 KB Output is correct
2 Correct 91 ms 16832 KB Output is correct
3 Correct 99 ms 14992 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 14772 KB Output is correct
2 Correct 102 ms 14720 KB Output is correct
3 Correct 70 ms 16128 KB Output is correct
4 Correct 33 ms 14820 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 14652 KB Output is correct
2 Correct 94 ms 16236 KB Output is correct
3 Correct 32 ms 13308 KB Output is correct
4 Correct 119 ms 15136 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14396 KB Output is correct
2 Correct 97 ms 14796 KB Output is correct
3 Correct 70 ms 14416 KB Output is correct
4 Correct 118 ms 15740 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 569 ms 30704 KB Output is correct
2 Correct 143 ms 19916 KB Output is correct
3 Correct 153 ms 18016 KB Output is correct
4 Correct 1246 ms 40880 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 534 ms 28860 KB Output is correct
2 Correct 173 ms 20928 KB Output is correct
3 Correct 74 ms 18440 KB Output is correct
4 Correct 1217 ms 42736 KB Output is correct