Submission #48543

#	Time	Username	Problem	Language	Result	Execution time	Memory
48543		tincamatei	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	493 ms	131212 KiB

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 (stderr)

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