oj.uz

답안 #48543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48543 2018-05-15T15:07:34 Z tincamatei 운세 보기 2 (JOI14_fortune_telling2) C++14
100 / 100
 493 ms 131212 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;
const int MAX_M = 200000;
const int MAX_COORD = 2 * MAX_N + MAX_M;

int a[MAX_N], b[MAX_N], query[MAX_M];
int realval[MAX_COORD];
int maxval;
int* p[MAX_COORD];

bool cmp(int *a, int *b) {
	return *a < *b;
}

void normalize(int n) {
	sort(p, p + n, cmp);
	int last = *p[0], j = 0;
	realval[0] = *p[0];
	for(int i = 0; i < n; ++i)
		if(*p[i] == last) {
			*p[i] = j;
		} else {
			last = *p[i];
      realval[++j] = last;
			*p[i] = j;
		}
  maxval = j;
}

int aint[1+MAX_COORD * 4];

void updateaint(int l, int r, int poz, int val, int nod = 1) {
	if(r < l || poz < l || r < poz)
		return;
	if(l == r)
		aint[nod] = val;
	else {
		int mid = (l + r) / 2;
	  updateaint(l, mid, poz, val, 2 * nod);
		updateaint(mid + 1, r, poz, val, 2 * nod + 1);
		aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
	}
}

int queryaint(int l, int r, int i, int j, int nod = 1) {
	if(j < l || r < i || r < l || j < i)
		return 0;
	else if(i <= l && r <= j)
		return aint[nod];
	else {
		int mid = (l + r) / 2;
		return max(queryaint(l, mid, i, j, 2 * nod), queryaint(mid + 1, r, i, j, 2 * nod + 1));
	}
}

struct Event {
	int mom, st, dr;
	int id;
}xd[MAX_M];

bool cmp2(Event a, Event b) {
  return a.mom < b.mom;
}

int aib[1+MAX_COORD];

static inline int lsb(int x) {
  return x & (-x);
}

void updateaib(int poz, int val) {
  ++poz;
  while(poz <= MAX_COORD) {
    aib[poz] += val;
    poz += lsb(poz);
  }
}

int queryaib(int poz) {
  ++poz;
  int r = 0;
  while(poz > 0) {
    r += aib[poz];
    poz -= lsb(poz);
  }
  return r;
}

int main() {
	int n, m, top = 0;
	long long rez = 0LL;
#ifdef HOME
	freopen("fortune.in", "r", stdin);
	freopen("fortune.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; ++i) {
		scanf("%d%d", &a[i], &b[i]);
		p[top++] = &a[i];
		p[top++] = &b[i];
	}
	for(int i = 0; i < m; ++i) {
		scanf("%d", &query[i]);
		p[top++] = &query[i];
	}

	normalize(top);

	for(int i = 0; i < m; ++i)
		updateaint(0, maxval, query[i], i + 1);
	for(int i = 0; i < n; ++i) {
		xd[i].st = min(a[i], b[i]);
		xd[i].dr = max(a[i], b[i]);
		xd[i].mom = queryaint(0, maxval, xd[i].st, xd[i].dr - 1);
		xd[i].id = i;
	}
	sort(xd, xd + n, cmp2);
	int lastup = n;
	for(int i = m; i > 0; --i) {
    while(lastup - 1 >= 0 && xd[lastup - 1].mom >= i) {
      --lastup;
      int infata = queryaib(maxval) - queryaib(xd[lastup].dr - 1);
      if(infata % 2 == 0)
        rez = rez + realval[xd[lastup].dr];
      else
        rez = rez + realval[xd[lastup].st];
    }
    updateaib(query[i - 1], 1);
	}
	while(lastup - 1 >= 0) {
    --lastup;
    int infata = queryaib(maxval) - queryaib(xd[lastup].dr - 1);
    if(infata % 2 == 0)
      rez = rez + realval[a[xd[lastup].id]];
    else
      rez = rez + realval[b[xd[lastup].id]];
	}
	//scapi de hacer
	//dai de cancer
  printf("%lld", rez);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &query[i]);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 780 KB Output is correct
6 Correct 3 ms 780 KB Output is correct
7 Correct 3 ms 800 KB Output is correct
8 Correct 3 ms 840 KB Output is correct
9 Correct 3 ms 872 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct
13 Correct 3 ms 1172 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2248 KB Output is correct
2 Correct 36 ms 3964 KB Output is correct
3 Correct 55 ms 6044 KB Output is correct
4 Correct 75 ms 7936 KB Output is correct
5 Correct 76 ms 9224 KB Output is correct
6 Correct 75 ms 10400 KB Output is correct
7 Correct 77 ms 11544 KB Output is correct
8 Correct 76 ms 12616 KB Output is correct
9 Correct 61 ms 12984 KB Output is correct
10 Correct 58 ms 13192 KB Output is correct
11 Correct 56 ms 13592 KB Output is correct
12 Correct 57 ms 15184 KB Output is correct
13 Correct 58 ms 15888 KB Output is correct
14 Correct 71 ms 17316 KB Output is correct
15 Correct 64 ms 18496 KB Output is correct
16 Correct 69 ms 19924 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 24588 KB Output is correct
2 Correct 232 ms 31852 KB Output is correct
3 Correct 304 ms 38424 KB Output is correct
4 Correct 480 ms 53872 KB Output is correct
5 Correct 152 ms 53872 KB Output is correct
6 Correct 471 ms 61564 KB Output is correct
7 Correct 489 ms 67404 KB Output is correct
8 Correct 452 ms 73248 KB Output is correct
9 Correct 444 ms 79108 KB Output is correct
10 Correct 493 ms 84832 KB Output is correct
11 Correct 472 ms 90416 KB Output is correct
12 Correct 480 ms 96256 KB Output is correct
13 Correct 478 ms 102016 KB Output is correct
14 Correct 336 ms 102216 KB Output is correct
15 Correct 336 ms 107948 KB Output is correct
16 Correct 340 ms 114240 KB Output is correct
17 Correct 340 ms 114876 KB Output is correct
18 Correct 304 ms 115816 KB Output is correct
19 Correct 382 ms 125412 KB Output is correct
20 Correct 375 ms 131212 KB Output is correct