oj.uz

답안 #399826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399826 2021-05-06T17:36:15 Z nikatamliani 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 11 ms 19916 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+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;
bool is_flipped[N];
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]) {
			is_flipped[i] = query(max(a[i], b[i]), N-1, SUM) % 2;
		}
		update(t[r], 1, SUM);
	}
	for(int i = 1; i <= n; ++i) {
		if(is_flipped[i]) {
			sum += save_b[i];
		} else {
			sum += save_a[i];
		}
	}
	cout << sum << endl;
}

Compilation message

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

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -