제출 #372911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372911		Ahoora	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	558 ms	58076 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;

const int N = 3 * 2 * 1000 * 100 + 10, LG = 20;
int n, k, a[N], b[N], t[N], mn[N], sz, seg[N << 2], fen[N], fl[N];
vector<int> add[N];
vector<pair<int, int>> query[N];

inline void build(int l = 0, int r = sz, int id = 1) {
	if (l + 1 == r) {
		seg[id] = mn[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, id << 1), build(mid, r, id << 1 | 1);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

inline int get(int s, int e, int l = 0, int r = sz, int id = 1) {
	if (s <= l && e >= r)
		return seg[id];
	if (s >= r || e <= l)
		return k;
	int mid = l + r >> 1;
	return min(get(s, e, l, mid, id << 1), get(s, e, mid, r, id << 1 | 1));
}

inline void upd(int x) {
	for (++x; x < N; x += x & -x)
		fen[x]++;
}

inline int GET(int x) {
	int res = 0;
	for (; x; x -= x & -x)
		res += fen[x];
	return res;
}

inline int inp() {
	int res = 0;
	char c = '0';
	while (c >= '0' && c <= '9') {
		((res *= 10) += c - '0');
		c = getchar();
	}
	return res;
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	n = inp(), k = inp();
	vector<int> all;
	for (int i = 0; i < n; i++) {
		a[i] = inp(), b[i] = inp();
		for (auto x: {a[i], b[i]})
			all.push_back(x);
	}
	for (int i = 0; i < k; i++)
		t[i] = inp(), all.push_back(t[i]);
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end()) - all.begin());
	for (int i = 0; i < n; i++)
		for (auto x: {&a[i], &b[i]})
			*x = lower_bound(all.begin(), all.end(), *x) - all.begin();
	for (int i = 0; i < k; i++)
		t[i] = lower_bound(all.begin(), all.end(), t[i]) - all.begin();
	reverse(t, t + k);
	sz = (int)(all.size());
	for (int i = 0; i < sz; i++)
		mn[i] = k;
	for (int i = 0; i < k; i++) 
		mn[t[i]] = min(mn[t[i]], i);
	build();
	for (int i = 0; i < k; i++)
		add[t[i]].push_back(i);
	for (int i = 0; i < n; i++) {
		if (a[i] > b[i])
			swap(a[i], b[i]), fl[i]++;
		int ind = get(a[i], b[i]);
		query[b[i]].push_back({i, ind});
	}
	long long ans = 0;
	for (int i = N - 1; i >= 0; i--) {
		for (auto it: add[i]) 
			upd(it);
		for (auto it: query[i]) {
			int ind = it.second, i = it.first;
			int res = GET(ind);
			if (ind == k) {
				fl[i] += res;
			} else {
				fl[i] = 0;
				fl[i] += res;
				swap(a[i], b[i]);
			}
			ans += (fl[i] & 1? all[b[i]]: all[a[i]]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

fortune_telling2.cpp: In function 'void build(int, int, int)':
fortune_telling2.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int mid = l + r >> 1;
      |            ~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int, int)':
fortune_telling2.cpp:24:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int mid = l + r >> 1;
      |            ~~^~~

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