oj.uz

답안 #52172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52172 2018-06-24T13:05:51 Z ainta 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 2000 ms 9848 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 524288
using namespace std;
int n, K;
struct point {
	int a, b;
}w[201000], ori[201000];
int X[401000], P[201000], Q[201000], IT[SZ+SZ];
vector<int>G[401000];
int BIT[SZ];
void Ins(int a, int b) {
	a += SZ;
	while (a) {
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
void Add(int a, int b) {
	while (a < SZ) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
int Max(int b, int e) {
	b += SZ, e += SZ;
	int r = 0;
	while (b <= e) {
		r = max(r, max(IT[b], IT[e]));
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
long long res;
int main() {
	int i, a;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
		X[i] = w[i].a, X[n + i] = w[i].b;
		ori[i] = w[i];
	}
	sort(X + 1, X + n + n + 1);
	for (i = 1; i <= n; i++) {
		w[i].a = lower_bound(X + 1, X + n + n + 1, w[i].a) - X;
		w[i].b = lower_bound(X + 1, X + n + n + 1, w[i].b) - X;
	}
	for (i = 1; i <= K; i++) {
		scanf("%d", &a);
		a = lower_bound(X + 1, X + n + n + 1, a + 1) - X - 1;
		Q[i] = a;
		Ins(a, i);
	}
	for (i = 1; i <= n; i++) {
		int mn = min(w[i].a, w[i].b), mx = max(w[i].a, w[i].b);
		G[Max(mn,mx-1)].push_back(i);
	}
	for (i = K; i >= 0; i--) {
		for (auto &x : G[i]) {
			int ck = ((K - i) - Sum(w[x].b - 1)) % 2;
			if (i) {
				if (ck)res += min(ori[x].a, ori[x].b);
				else res += max(ori[x].a, ori[x].b);
			}
			else {
				if (ck)res += ori[x].b;
				else res += ori[x].a;
			}
		}
		if (!i)break;
		Add(Q[i], 1);
	}
	printf("%lld\n", res);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2071 ms 9848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2071 ms 9848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2071 ms 9848 KB Time limit exceeded
2 Halted 0 ms 0 KB -