제출 #52173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52173		ainta	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	412 ms	130632 KiB

fortune_telling2

#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;
		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+1,mx)].push_back(i);
	}
	for (i = K; i >= 0; i--) {
		for (auto &x : G[i]) {
			int ck = ((K - i) - Sum(w[x].b)) % 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);
}

컴파일 시 표준 에러 (stderr) 메시지

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: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65