제출 #399844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399844		nikatamliani	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	539 ms	55452 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10, MAX = 0, SUM = 1;
int tree[4*N], a[N], b[N], t[N], save_a[N], save_b[N];
int n, k;
long long sum;
vector<int> q[N];
void maxi(int &x, int y) {
	if(x < y) x = y;
}
void update(int l, int r, int x, int val, int p, int type) {
	if(l > x || r < x) return;
	if(l == r) {
		if(type == MAX) {
			maxi(tree[p], val);
		} else if(type == SUM) {
			tree[p] += val;
		} else {
			assert(false);
		}
	} else {
		int m = l + r >> 1;
		update(l, m, x, val, p << 1, type);
		update(m+1, r, x, val, p << 1 | 1, type);
		if(type == MAX) {
			tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
		} else if(type == SUM) {
			tree[p] = tree[p << 1] + tree[p << 1 | 1];
		} else {
			assert(false);
		}
	}
}
int query(int l, int r, int L, int R, int p, int type) { 
	if(l > R || L > r) return 0;
	if(L <= l && R >= r) {
		return tree[p];
	}
	int m = l + r >> 1;
	int lft = query(l, m, L, R, p << 1, type);
	int rgh = query(m+1, r, L, R, p << 1 | 1, type);
	if(type == MAX) {
		return max(lft, rgh);
	} else if(type == SUM) {
		return lft+rgh;
	} else {
		assert(false);
	}
}
void update(int x, int val, int type) {
	update(1, N-1, x, val, 1, type);
}
int query(int l, int r, int type) {
	return query(1, N-1, l, r, 1, type);
}
void compress(vector<int*> &coords) {
	int cnt = 0, prv = -1;
	sort(coords.begin(), coords.end(), [](int* x, int *y) {
		return *x < *y;
	});
	for(int i = 0; i < (int)coords.size(); ++i) {
		if(prv < *coords[i]) ++cnt;
		prv = *coords[i];
		*coords[i] = cnt;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		if(a[i] == b[i]) {
			sum += a[i];
			--i;
			--n;
		}
	}
	if(n == 0) {
		cout << sum << endl;
		return 0;
	}
	vector<int*> coords;
	for(int i = 1; i <= k; ++i) {
		cin >> t[i];
		coords.push_back(&t[i]);
	}
	for(int i = 1; i <= n; ++i) {
		save_a[i] = a[i];
		save_b[i] = b[i];
		coords.push_back(&a[i]);
		coords.push_back(&b[i]);
	}
	compress(coords);
	for(int i = 1; i <= k; ++i) {
		update(t[i], i, MAX);
	}
	for(int i = 1; i <= n; ++i) {
		int r = query(min(a[i], b[i]), max(a[i], b[i])-1, MAX);
		q[r].push_back(i);
	}
	memset(tree, 0, sizeof tree);
	for(int r = k; r >= 0; --r) {
		for(int i : q[r]) {
			int parity = query(max(a[i], b[i]), N-1, SUM) % 2;
			if(r > 0) {
				parity ^= a[i] < b[i];
			}
			sum += parity ? save_b[i] : save_a[i];
		}
		update(t[r], 1, SUM);
	}
	cout << sum << endl;
}

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

fortune_telling2.cpp: In function 'void update(int, int, int, int, int, int)':
fortune_telling2.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int m = l + r >> 1;
      |           ~~^~~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int, int)':
fortune_telling2.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65