Submission #900783

#	Time	Username	Problem	Language	Result	Execution time	Memory
900783		Amaarsaa	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	5 ms	31308 KiB

fortune_telling2

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
const int N = 2e5 + 2, NN = 2e6 + 2;
ll a[N], b[N], t[N], A[N], B[N], T[N], S[NN], ST[NN];
vector < ll > V[N];
bool Changed[N] = {false};
map < int , int > M;
ll mid;

void Update(ll p, ll lo, ll hi, ll ind, ll x) {
	if ( lo == hi) {
//		cout << lo << " " << hi << " " << ind << endl;
		S[p] = x;
		return ;
	}
	mid = (lo + hi)/2;
	if ( ind <= mid) Update(2 * p, lo, mid, ind, x);
	else Update(2 * p + 1, mid + 1, hi, ind, x);
	S[p]= max(S[2 * p], S[2 *p + 1]);
}
ll Find(ll p, ll lo, ll hi, ll l, ll r) {
//	cout << lo << " " << hi << " " << l << " " << r << endl;
	if ( l > r) return 0;
	if ( lo >= l && hi <= r) return S[p];
	if ( hi < l || lo > r) return 0;
	mid = (lo + hi)/2;
	if ( l== 3 && r == 6 ) cout << lo << " " << hi << " " << max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r)) << endl;
	return max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r));
}
void update(ll p, ll lo, ll hi, ll ind) {
	if ( lo == hi) {
		ST[p] ++;
		return ;
	}
	mid = (lo + hi)/2;
	if ( ind <= mid) update(2 * p, lo, mid, ind);
	else update(2 * p + 1, mid + 1, hi, ind);
	ST[p]= ST[2 * p] +ST[2 *p + 1];
}
ll find(ll p, ll lo, ll hi, ll l, ll r) {
	if ( lo >= l && hi <= r) return ST[p];
	if ( hi < l || lo > r) return 0;
	mid = (lo + hi)/2;
	return find(2 * p, lo, mid, l, r) + find(2 * p + 1, mid + 1, hi, l, r);
}

int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m, ans, s, sum, x, y, r, p, i, j;

	cin >> n >> m;
	
	vector < pair < ll, pair < ll, ll > > > v;
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i] >> b[i];
		if ( a[i] > b[i]) {
			swap(a[i], b[i]);
			Changed[i] = 1;
		}
		v.push_back({a[i], {i, 1}});
		v.push_back({b[i], {i, 2}});
	}
	for (i = 1; i <= m; i++){
		cin >> t[i]; 
		v.push_back({t[i], {i, 3}});
	}
	sort(v.begin(), v.end());
	
	r = 1;
	for (i = 0; i < v.size(); i ++) {
		if ( M[v[i].first] == 0) {
			M[v[i].first] = r;
			r ++;
		}
		if ( v[i].second.second == 1) {
			A[v[i].second.first] = M[v[i].first];
		}
		if ( v[i].second.second == 2) {
			B[v[i].second.first] = M[v[i].first];
		}
		if ( v[i].second.second == 3) {
			T[v[i].second.first] = M[v[i].first];
		}
		
	}
	for (i = 1; i <= m; i ++) {
		Update(1, 1, 6e5, T[i], i);
	}
	for (i = 1; i <= n; i ++) {
	//	cout << A[i] << " " << B[i] << endl << endl;
		s = Find(1, 1, 6e5, A[i], B[i] - 1);
	//	cout << s << endl << endl;
		V[s].push_back(i);
	}
	ll Ans[N];
	sum =0;
	for (i = m; i >= 0; i --) {
		for (j = 0; j < V[i].size(); j ++) {
			r = V[i][j];
			Ans[r]= find(1, 1, NN, B[r], NN);
	//		cout << r << " " << Ans[r] << " " << i << endl;
			if ( Ans[r] % 2 == 0) {
				if ( i == 0 && Changed[r]) sum += b[r];
				else sum += a[r];
			}
			else {
				if ( i == 0 && Changed[r]) sum += b[r];
				else sum += a[r];
			}
		}
		if (i == 0) continue;
		update(1, 1, NN, t[i]);
	}
	
	cout << sum << endl;
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:76:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (i = 0; i < v.size(); i ++) {
      |              ~~^~~~~~~~~~
fortune_telling2.cpp:104:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (j = 0; j < V[i].size(); j ++) {
      |               ~~^~~~~~~~~~~~~
fortune_telling2.cpp:54:11: warning: unused variable 'ans' [-Wunused-variable]
   54 |  ll n, m, ans, s, sum, x, y, r, p, i, j;
      |           ^~~
fortune_telling2.cpp:54:24: warning: unused variable 'x' [-Wunused-variable]
   54 |  ll n, m, ans, s, sum, x, y, r, p, i, j;
      |                        ^
fortune_telling2.cpp:54:27: warning: unused variable 'y' [-Wunused-variable]
   54 |  ll n, m, ans, s, sum, x, y, r, p, i, j;
      |                           ^
fortune_telling2.cpp:54:33: warning: unused variable 'p' [-Wunused-variable]
   54 |  ll n, m, ans, s, sum, x, y, r, p, i, j;
      |                                 ^

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