Submission #118824

#	Time	Username	Problem	Language	Result	Execution time	Memory
118824		roseanne_pcy	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1491 ms	125264 KiB

fortune_telling2

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n, m;

const int maxn = 2e5+5;

struct node
{
	int val;
	node *left, *right;
	node(int a, node *b, node *c)
	{
		val = a;
		left = b;
		right = c;
	}
	node* insert(int x, int L = 0, int R = m-1) 
	{
		if(L<= x && x<= R)
		{
			if(L == R) return new node(val+1, NULL, NULL);
			int M = (L+R)/2;
			return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R));
		}
		return this;
	}
	int ask(int i, int j, int L = 0, int R = m-1)
	{
		if(i> R || j< L) return 0;
		if(i<= L && R<= j) return val;
		int M = (L+R)/2;
		int x = left->ask(i, j, L, M);
		int y = right->ask(i, j, M+1, R);
		return x+y;
	}
};

node* zero = new node(0, NULL, NULL);

int A[maxn], B[maxn];

int op[maxn];
node* ps[maxn];
vector< ii > foo;

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i<= n; i++) scanf("%d %d", &A[i], &B[i]);
	zero->left = zero->right = zero;
	for(int i = 0; i< m; i++)
	{
		scanf("%d", &op[i]);
		foo.pb(ii(op[i], i));
	}
	sort(foo.begin(), foo.end());
	ps[m] = zero;
	for(int i = m-1; i>= 0; i--)
	{
		ps[i] = ps[i+1];
		ps[i] = ps[i]->insert(foo[i].Y);
		// printf("insert %d\n", foo[i].Y);
	}
	ll ans = 0;
	for(int i = 1; i<= n; i++)
	{
		int a = A[i], b = B[i];
		if(a> b) swap(a, b);
		int pa = lower_bound(foo.begin(), foo.end(), ii(a, 0))-foo.begin();
		int pb = lower_bound(foo.begin(), foo.end(), ii(b, 0))-foo.begin();
		// printf("pa pb %d %d\n", pa, pb);
		int lo = 0, hi = m-1;
		while(lo< hi)
		{
			int mid = (lo+hi+1)/2;
			if((ps[pa])->ask(mid, m-1) == (ps[pb])->ask(mid, m-1)) hi = mid-1;
			else lo = mid;
		}
		// printf("lo = %d\n", lo);
		if(ps[pa]->ask(lo, m-1) == ps[pb]->ask(lo, m-1)) 
		{
			int swaps = ps[pa]->ask(0, m-1);
			if(swaps%2) ans += B[i];
			else ans += A[i];
			continue;
		}
		int swaps = ps[pa]->ask(lo+1, m-1);
		// printf("swaps %d\n", swaps);
		if(swaps%2) ans += a;
		else ans += b;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56: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:57:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%d %d", &A[i], &B[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op[i]);
   ~~~~~^~~~~~~~~~~~~~

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