Submission #48543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48543	2018-05-15T15:07:34 Z	tincamatei	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	493 ms	131212 KB

fortune_telling2

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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