제출 #605641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605641		1ne	새로운 문제 (POI11_met)	C++14	74 / 100	418 ms	65536 KiB

met

#include <bits/stdc++.h> 

using namespace std;

#define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)

enum EventType { KTYPE, MTYPE, NTYPE };
struct event {
	int type, val, pos, idx;
	
	event(int t, int v, int p, int i) : type(t), val(v), pos(p), idx(i) {} 
	bool operator< (const event& ot) const {
		return make_pair(pos, type) < make_pair(ot.pos, ot.type);
	}
};

int n, m, k;
vector< event > events;
long long contains[310000];
int target[310000];
int ans[310000];

void rec(int minq, int maxq, vector<event> &events) {
	if (minq == maxq) {
		for (event e : events) if (e.type == NTYPE) ans[e.val] = minq;
		return;
	}

	int mid = (minq+maxq)/2;
	
	// process events
	long long curval = 0;
	for (event e : events) {
		if (e.type == NTYPE) contains[e.val] = 0;
		if (e.type == MTYPE) {
			contains[e.val] += curval;
			if (contains[e.val] > 1000000000) contains[e.val] = 1000000000;
		}
		if (e.type == KTYPE && e.idx <= mid) curval += e.val;
	}

	// split events into two halves
	vector<event> events_left, events_right;
	for (event e : events) {
		if (e.type == NTYPE || e.type == MTYPE) {
			if (contains[e.val] >= target[e.val]) {
				events_left.push_back(e);
			}
			else {
				target[e.val] -= contains[e.val];
				contains[e.val] = 0;
				events_right.push_back(e);
			}
		}

		else {
			if (e.idx <= mid) events_left.push_back(e);
			else events_right.push_back(e);
		}
	}

	rec(minq, mid, events_left);
	rec(mid+1, maxq, events_right);
}

int main() {
	scanf("%d %d", &n, &m);
	
	REP(i,n) {
		events.emplace_back((int)NTYPE, i, -1, -1);
	}

	REP(i,m) {
		int owner;
		scanf("%d", &owner); owner--;
		events.emplace_back((int)MTYPE, owner, i, -1);
	}

	REP(i,n) scanf("%d", &target[i]);

	scanf("%d", &k);
	REP(i,k) {
		int l, r, a;
		scanf("%d %d %d", &l, &r, &a); l--; r--;

		events.emplace_back((int)KTYPE, a, l, i);
		events.emplace_back((int)KTYPE, -a, r+1, i);
		if (l > r) {
			events.emplace_back((int)KTYPE, a, 0, i);
			events.emplace_back((int)KTYPE, -a, m, i);
		}
	}

	sort(events.begin(), events.end());
	rec(0, k, events);

	REP(i,n) {
		if (ans[i] < k) printf("%d\n", ans[i]+1);
		else printf("NIE\n");
	}
}

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

met.cpp: In function 'int main()':
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
      |                         ^
met.cpp:69:2: note: in expansion of macro 'REP'
   69 |  REP(i,n) {
      |  ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
      |                         ^
met.cpp:73:2: note: in expansion of macro 'REP'
   73 |  REP(i,m) {
      |  ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
      |                         ^
met.cpp:79:2: note: in expansion of macro 'REP'
   79 |  REP(i,n) scanf("%d", &target[i]);
      |  ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
      |                         ^
met.cpp:82:2: note: in expansion of macro 'REP'
   82 |  REP(i,k) {
      |  ^~~
met.cpp:5:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
      |                         ^
met.cpp:97:2: note: in expansion of macro 'REP'
   97 |  REP(i,n) {
      |  ^~~
met.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d", &owner); owner--;
      |   ~~~~~^~~~~~~~~~~~~~
met.cpp:79:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  REP(i,n) scanf("%d", &target[i]);
      |           ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
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", &l, &r, &a); l--; r--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 13
• Subtask 8: 0 / 13