답안 #34676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34676 2017-11-15T00:47:06 Z cheater2k 운세 보기 2 (JOI14_fortune_telling2) C++14
100 / 100
263 ms 11008 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, k;
int a[N], b[N], t[N];
vector<int> z, vec, v;
int res[N], lst[N];
long long ans;

// BIT
int T[N];
void merge(int type, int &x, int y) {
	if (type == 0) x = max(x, y); else x += y;
}
void upd(int type, int x, int v) { for (; x > 0; x -= x & -x) merge(type, T[x], v); }
int get(int type, int x) { int res = 0; for (; x < N; x += x & -x) merge(type, res, T[x]); return res; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	for (int i = 1; i <= k; ++i) {
		cin >> t[i];
		z.push_back(t[i]);
		vec.push_back(i);
	}
	sort(z.begin(), z.end());
	z.resize(distance(z.begin(), unique(z.begin(), z.end())));
	sort(vec.begin(), vec.end(), [&](int x, int y) {
		return t[x] < t[y];
	});

	for (int i = 1; i <= n; ++i) {
		if (a[i] > b[i]) swap(a[i], b[i]), res[i] = 1;
		v.push_back(i);
	}
	sort(v.begin(), v.end(), [&](int x, int y) {
		return b[x] < b[y];
	});

	int pt = 0;
	for (int i = 0; i < v.size(); ++i) {
		while(pt < vec.size() && t[vec[pt]] < b[v[i]]) {
			upd(0, lower_bound(z.begin(), z.end(), t[vec[pt]]) - z.begin() + 1, vec[pt]);
			++pt;
		}
		int A = lower_bound(z.begin(), z.end(), a[v[i]]) - z.begin() + 1;
		lst[v[i]] = get(0, A);
	}

	memset(T, 0, sizeof T); // reset BIT

	pt = vec.size() - 1;
	for (int i = v.size()-1; i >= 0; --i) {
		while(pt >= 0 && b[v[i]] <= t[vec[pt]]) {
			upd(1, vec[pt], 1);
			--pt;
		}
		if (lst[v[i]] > 0) res[v[i]] = 1;
		int cur = get(1, lst[v[i]] + 1);
		res[v[i]] ^= (cur & 1);
	}

	for (int i = 1; i <= n; ++i) {
		ans += (res[i] == 0 ? a[i] : b[i]);
	}

	cout << ans << '\n';
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i) {
                    ^
fortune_telling2.cpp:45:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pt < vec.size() && t[vec[pt]] < b[v[i]]) {
            ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6868 KB Output is correct
2 Correct 0 ms 6868 KB Output is correct
3 Correct 0 ms 6868 KB Output is correct
4 Correct 0 ms 6868 KB Output is correct
5 Correct 0 ms 6868 KB Output is correct
6 Correct 0 ms 6868 KB Output is correct
7 Correct 0 ms 6868 KB Output is correct
8 Correct 0 ms 6868 KB Output is correct
9 Correct 0 ms 6868 KB Output is correct
10 Correct 0 ms 6868 KB Output is correct
11 Correct 0 ms 6868 KB Output is correct
12 Correct 0 ms 6868 KB Output is correct
13 Correct 0 ms 6868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7180 KB Output is correct
2 Correct 19 ms 7292 KB Output is correct
3 Correct 33 ms 7292 KB Output is correct
4 Correct 36 ms 7808 KB Output is correct
5 Correct 39 ms 7808 KB Output is correct
6 Correct 39 ms 7808 KB Output is correct
7 Correct 36 ms 7808 KB Output is correct
8 Correct 33 ms 7808 KB Output is correct
9 Correct 26 ms 7808 KB Output is correct
10 Correct 29 ms 7808 KB Output is correct
11 Correct 29 ms 7808 KB Output is correct
12 Correct 26 ms 7808 KB Output is correct
13 Correct 36 ms 7808 KB Output is correct
14 Correct 36 ms 7808 KB Output is correct
15 Correct 36 ms 7808 KB Output is correct
16 Correct 39 ms 7808 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 9600 KB Output is correct
2 Correct 133 ms 9600 KB Output is correct
3 Correct 183 ms 9980 KB Output is correct
4 Correct 263 ms 11008 KB Output is correct
5 Correct 93 ms 9600 KB Output is correct
6 Correct 236 ms 11008 KB Output is correct
7 Correct 246 ms 11008 KB Output is correct
8 Correct 233 ms 11008 KB Output is correct
9 Correct 206 ms 11008 KB Output is correct
10 Correct 249 ms 11008 KB Output is correct
11 Correct 223 ms 11008 KB Output is correct
12 Correct 193 ms 11008 KB Output is correct
13 Correct 216 ms 11008 KB Output is correct
14 Correct 149 ms 11008 KB Output is correct
15 Correct 143 ms 11008 KB Output is correct
16 Correct 136 ms 11008 KB Output is correct
17 Correct 156 ms 11008 KB Output is correct
18 Correct 146 ms 11008 KB Output is correct
19 Correct 183 ms 11008 KB Output is correct
20 Correct 173 ms 11008 KB Output is correct