답안 #36016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36016 2017-12-04T08:29:23 Z minkank 운세 보기 2 (JOI14_fortune_telling2) C++14
100 / 100
363 ms 78560 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, m, a[N], b[N], c[N], last[21][3 * N], lg[3 * N], bit[3 * N];
vector<int> Value, Query[3 * N];
long long ans;

void upd(int pos) {
	for(pos; pos > 0; pos -= pos & -pos) bit[pos]++;
}

int get(int pos) {
	int res = 0;
	for(pos; pos < 3 * N; pos += pos & -pos) res += bit[pos];
	return res;
}

void getint(int &x) {
	x = 0;
	char c = getchar();
	while('0' > c || c > '9') c = getchar();
	while('0' <= c && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
}

int main() {
	getint(n); getint(m);
	lg[1] = 0;
	for(int i = 2; i < 3 * N; ++i) lg[i] = lg[i / 2] + 1;
	for(int i = 1; i <= n; ++i) getint(a[i]), getint(b[i]), Value.push_back(a[i]), Value.push_back(b[i]);
	for(int i = 1; i <= m; ++i) getint(c[i]), Value.push_back(c[i]);
	Value.push_back(0);
	sort(Value.begin(), Value.end());
	Value.resize(distance(Value.begin(), unique(Value.begin(), Value.end())));
	for(int i = 1; i <= n; ++i) 
		a[i] = lower_bound(Value.begin(), Value.end(), a[i]) - Value.begin() + 1,
		b[i] = lower_bound(Value.begin(), Value.end(), b[i]) - Value.begin() + 1;
	for(int i = 1; i <= m; ++i)
		c[i] = lower_bound(Value.begin(), Value.end(), c[i]) - Value.begin() + 1;
	for(int i = m; i >= 1; --i) if(!last[0][c[i]]) last[0][c[i]] = i;
	for(int i = 1; i <= 20; ++i) for(int j = 1; j < 3 * N; ++j)
		last[i][j] = max(last[i - 1][j], last[i - 1][j + (1 << (i - 1))]);
	for(int i = 1; i <= n; ++i) {
		if(a[i] == b[i]) {
			ans += Value[a[i] - 1];
			continue;
		}
		int mn = min(a[i], b[i]), mx = max(a[i], b[i]) - 1;
		int pos = max(last[lg[mx - mn + 1]][mn], last[lg[mx - mn + 1]][mx - (1 << lg[mx - mn + 1]) + 1]);
		Query[pos].push_back(i);
	}
	for(int i = m; i >= 0; --i) {
		for(auto j: Query[i]) {
			if(i && a[j] < b[j]) swap(a[j], b[j]);
			if(get(a[j]) & 1) ans += Value[b[j] - 1];
			else ans += Value[a[j] - 1];
		}
		upd(c[i]);
	}
	printf("%lld", ans);
}

Compilation message

fortune_telling2.cpp: In function 'void upd(int)':
fortune_telling2.cpp:11:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos > 0; pos -= pos & -pos) bit[pos]++;
         ^
fortune_telling2.cpp: In function 'int get(int)':
fortune_telling2.cpp:16:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos < 3 * N; pos += pos & -pos) res += bit[pos];
         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 72332 KB Output is correct
2 Correct 16 ms 72332 KB Output is correct
3 Correct 19 ms 72332 KB Output is correct
4 Correct 23 ms 72332 KB Output is correct
5 Correct 26 ms 72332 KB Output is correct
6 Correct 26 ms 72332 KB Output is correct
7 Correct 23 ms 72332 KB Output is correct
8 Correct 16 ms 72332 KB Output is correct
9 Correct 26 ms 72332 KB Output is correct
10 Correct 16 ms 72332 KB Output is correct
11 Correct 13 ms 72332 KB Output is correct
12 Correct 19 ms 72332 KB Output is correct
13 Correct 29 ms 72332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 72604 KB Output is correct
2 Correct 43 ms 72840 KB Output is correct
3 Correct 59 ms 73184 KB Output is correct
4 Correct 76 ms 73184 KB Output is correct
5 Correct 69 ms 73236 KB Output is correct
6 Correct 63 ms 73184 KB Output is correct
7 Correct 76 ms 73192 KB Output is correct
8 Correct 69 ms 73436 KB Output is correct
9 Correct 46 ms 73184 KB Output is correct
10 Correct 66 ms 73184 KB Output is correct
11 Correct 59 ms 73212 KB Output is correct
12 Correct 53 ms 73436 KB Output is correct
13 Correct 69 ms 73184 KB Output is correct
14 Correct 66 ms 73184 KB Output is correct
15 Correct 76 ms 73224 KB Output is correct
16 Correct 76 ms 73288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 73952 KB Output is correct
2 Correct 173 ms 75488 KB Output is correct
3 Correct 236 ms 75488 KB Output is correct
4 Correct 316 ms 78560 KB Output is correct
5 Correct 119 ms 73952 KB Output is correct
6 Correct 336 ms 78560 KB Output is correct
7 Correct 363 ms 78560 KB Output is correct
8 Correct 349 ms 78560 KB Output is correct
9 Correct 323 ms 78560 KB Output is correct
10 Correct 329 ms 78560 KB Output is correct
11 Correct 329 ms 78560 KB Output is correct
12 Correct 326 ms 78560 KB Output is correct
13 Correct 289 ms 78560 KB Output is correct
14 Correct 219 ms 78560 KB Output is correct
15 Correct 203 ms 78560 KB Output is correct
16 Correct 199 ms 78560 KB Output is correct
17 Correct 219 ms 78560 KB Output is correct
18 Correct 223 ms 78560 KB Output is correct
19 Correct 266 ms 78560 KB Output is correct
20 Correct 246 ms 78560 KB Output is correct