제출 #548547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548547		2fat2code	새로운 문제 (POI11_met)	C++17	100 / 100	1246 ms	42736 KiB

met

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13