oj.uz

답안 #112170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112170 2019-05-17T17:05:51 Z kimjg1119 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 5 ms 1536 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <functional>
#define x first
#define y second


using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
typedef long long ll;

typedef struct node {
	int le, ri;
	int val;
}node;

typedef struct SegmentTree {
	vector<node> N;
	int root, n;
	int alloc() {
		N.push_back({ -1,-1,0 });
		return (int)N.size()-1;
	}
	SegmentTree(int _n) : n(_n) {
		root = alloc();
	}
	void update(int nx, int st, int en, int idx, int val) {
		if (st == en && idx == st) {
			N[nx].val = max(N[nx].val, val);
			return;
		}
		else if (idx < st || en < idx) return;
		int mid = ((ll)st + (ll)en) / 2;
		if (N[nx].le == -1) {
			int t = alloc();
			N[nx].le = t;
		}
		if (N[nx].ri == -1) {
			int t = alloc();
			N[nx].ri = t;
		}
		update(N[nx].le, st, mid, idx, val);
		update(N[nx].ri, mid + 1, en, idx, val);
		N[nx].val = max(N[N[nx].le].val, N[N[nx].ri].val);
	}
	void update(int idx, int val) {
		return update(root, 0, n - 1, idx, val);
	}
	int query(int nx, int st, int en, int le, int ri) {
		if (nx == -1) return 0;
		if (le <= st && en <= ri) return N[nx].val;
		else if (ri < st || en < le) return 0;
		int mid = ((ll)st + (ll)en) / 2;
		return max(query(N[nx].le, st, mid, le, ri), query(N[nx].ri, mid + 1, en, le, ri));
	}
	int query(int le, int ri) {
		return query(root, 0, n - 1, le, ri);
	}
}ST;

int tree[200005];
void update(int idx) {
	for (int i = idx; i < 200005; i += (i&-i))
		tree[i] += 1;
}
int query(int idx) {
	int s = 0;
	for (int i = idx; i > 0; i -= (i&-i))
		s += tree[i];
	return s;
}

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	vector<pii> V, Q;
	for (int i = 0; i < n; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		V.emplace_back(t1, t2);
	}
	sort(V.begin(), V.end(), [&](pii a, pii b) {
		return min(a.x, a.y) > min(b.x, b.y);
	});
	for (int i = 0; i < k; i++) {
		int t;
		scanf("%d", &t);
		Q.emplace_back(t, i+1);
	}
	sort(Q.begin(), Q.end(), greater<pii>());

	int last = 0;
	ll ans = 0;
	ST S(2 * 1e9 + 5);
	for (int i = 0; i < V.size(); i++) {
		int a = min(V[i].x, V[i].y), b = max(V[i].x, V[i].y);
		while (last < Q.size()) {
			if (Q[last].x >= a) {
				S.update(Q[last].x, Q[last].y);
				update(Q[last].y);
				last++;
			}
			else break;
		}
		int bound = S.query(a, b - 1);
		if (!bound) {
			ans += a;
			continue;
		}
		int ret = query(200000) - query(bound);
		if (ret % 2) ans += a;
		else ans += b;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
fortune_telling2.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (last < Q.size()) {
          ~~~~~^~~~~~~~~~
fortune_telling2.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
   ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Incorrect 5 ms 1280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Incorrect 5 ms 1280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Incorrect 5 ms 1280 KB Output isn't correct
5 Halted 0 ms 0 KB -