Submission #109090

#	Time	Username	Problem	Language	Result	Execution time	Memory
109090		njchung99	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	966 ms	57424 KiB

fortune_telling2

#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
vector<ll> vt;
ll getidx(ll x) {
	return lower_bound(vt.begin(), vt.end(), x) - vt.begin();
}
ll seg[2400000];
ll seg1[2400000];
ll dap[200010];
ll update(ll pos, ll val, ll node, ll x, ll y) {
	if (pos < x || y < pos)return seg[node];
	if (x == y)return seg[node] += val;
	ll mid = (x + y) / 2;
	return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
	if (hi < x || y < lo)return 0;
	if (lo <= x && y <= hi)return seg[node];
	ll mid = (x + y) / 2;
	return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
ll update1(ll pos, ll val, ll node, ll x, ll y) {
	if (pos < x || y < pos)return seg1[node];
	if (x == y)return seg1[node] =max( val,seg1[node]);
	ll mid = (x + y) / 2;
	return seg1[node] = max(update1(pos, val, node * 2, x, mid),update1(pos, val, node * 2 + 1, mid + 1, y));
}
ll query1(ll lo, ll hi, ll node, ll x, ll y) {
	if (hi < x || y < lo)return 0;
	if (lo <= x && y <= hi)return seg1[node];
	ll mid = (x + y) / 2;
	return max(query1(lo, hi, node * 2, x, mid),query1(lo, hi, node * 2 + 1, mid + 1, y));
}
ll n, m;
pair<ll, ll> a[200100];
ll b[200010];
vector<pair<ll, ll>> vt1;
int main()
{
	scanf("%lld %lld", &n, &m);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld %lld", &a[i].first, &a[i].second);
		vt.push_back(a[i].first);
		vt.push_back(a[i].second);
	}
	for (ll i = 1; i <= m; i++) {
		scanf("%lld", &b[i]);
		vt.push_back(b[i]);
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for (ll i = 1; i <= m; i++) {
		b[i] = getidx(b[i]);
		update1(b[i], i, 1, 0, vt.size());
	}
	for (ll i = 1; i <= n; i++) {
		if (a[i].first != a[i].second) {
			ll xx=query1(getidx(min(a[i].first,a[i].second)), getidx(max(a[i].second,a[i].first)) - 1, 1, 0, vt.size());
			vt1.push_back({ xx, i});
		}
	}
	sort(vt1.begin(), vt1.end());
	ll idx = vt1.size() - 1;
	for (ll i = m; i >= 1; i--) {
		update(b[i], 1, 1, 0, vt.size());
		while (1) {
			if (idx==-1)break;
			if (vt1[idx].first != i)break;
			ll curr = vt1[idx].second;
			ll gap=query(getidx(max(a[curr].second,a[curr].first)), vt.size(), 1, 0, vt.size());
			if (gap % 2)
				dap[curr] = min(a[curr].first, a[curr].second);
			else
				dap[curr] = max(a[curr].first, a[curr].second);
			idx--;
		}
	}
	while (1) {
		if (idx == -1)break;
		ll curr = vt1[idx].second;
		ll gap = query(getidx(a[curr].second), vt.size(), 1, 0, vt.size());
		if (gap % 2)
			dap[curr] = a[curr].second;
		else
			dap[curr] = a[curr].first;
		idx--;
	}
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		if (dap[i])
			sum += dap[i];
		else
			sum += a[i].first;
	}
	printf("%lld\n", sum);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &b[i]);
   ~~~~~^~~~~~~~~~~~~~~

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