Submission #52271

#	Time	Username	Problem	Language	Result	Execution time	Memory
52271		ics0503	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	479 ms	39020 KiB

fortune_telling2

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { long long x, y; }a[412121];
bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; }
long long Q[412121], ALL[414141], an, tn, tree[2121212], P[412121];
vector<long long>T[412121], R;
long long oper(long long a, long long b, long long tp) {if (tp == 1) { if (a < b)return b; return a; }else return a + b;}
void insert_g(long long w, long long g, long long tp) { for (long long i = w + tn; i > 0; i /= 2)tree[i] = oper(tree[i], g, tp); }
long long search_g(long long ss, long long ee,long long tp) {
	long long s = ss + tn, e = ee + tn, res = tp==1?-1:0;
	while (s <= e) {
		if (s % 2 == 1)res = oper(res, tree[s++],tp);
		if (e % 2 == 0)res = oper(res, tree[e--],tp);
		s /= 2; e /= 2;
	}
	return res;
}
int main() {
	long long n, m, i, j; scanf("%lld%lld", &n, &m);
	for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
	for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
	sort(ALL, ALL + an);
	an = unique(ALL, ALL + an) - ALL;
	for (i = 0; i < n; i++)a[i] = { lower_bound(ALL, ALL + an, a[i].x) - ALL,lower_bound(ALL, ALL + an, a[i].y) - ALL };
	for (i = 0; i < m; i++)Q[i] = lower_bound(ALL, ALL + an, Q[i]) - ALL;
	for (tn = 1; tn < an; tn *= 2);
	for (i = 0; i < tn * 2; i++)tree[i] = -1;
	for (i = 0; i < m; i++)insert_g(Q[i], i,1);
	for (i = 0; i < n; i++) {
		long long s = min(a[i].x, a[i].y), e = max(a[i].x, a[i].y);
		P[i] = search_g(s, e - 1,1);
		if (P[i] == -1)R.push_back(i);
		else T[P[i]].push_back(i);
	}
	for (i = 0; i < tn * 2; i++)tree[i] = 0;
	long long ans = 0;
	for (i = m - 1; i >= 0; i--) {
		for (j = 0; j < T[i].size(); j++) {
			long long now = T[i][j];
			if (search_g(max(a[now].x, a[now].y), an - 1, 0) % 2 == 0)ans += ALL[max(a[now].x, a[now].y)];
			else ans += ALL[min(a[now].x, a[now].y)];
		}
		insert_g(Q[i], 1, 0);
	}
	for (i = 0; i < R.size(); i++) {
		long long now = R[i];
		if (search_g(a[now].x, an - 1, 0) % 2 == 0)ans += ALL[a[now].x];
		else ans += ALL[a[now].y];
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < T[i].size(); j++) {
               ~~^~~~~~~~~~~~~
fortune_telling2.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < R.size(); i++) {
              ~~^~~~~~~~~~
fortune_telling2.cpp:21:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, m, i, j; scanf("%lld%lld", &n, &m);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:22:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:23:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
                         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65