Submission #56736

#	Time	Username	Problem	Language	Result	Execution time	Memory
56736		Mamnoon_Siam	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	3020 ms	29196 KiB

fortune_telling2

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 200010;
const int inf = 2e9;

struct MaxSegTree {
	vector<int> t;
	MaxSegTree() {}
	MaxSegTree(int N) {t.assign(N << 1, -1);}
	void update(int p, int val) {
		p += (t.size() >> 1);
		t[p] = max(t[p], val);
		for(; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
	}
	int query(int l, int r) {
		r++;
		int ret = -inf;
		for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
			if(l & 1) ret = max(ret, t[l++]);
			if(r & 1) ret = max(ret, t[--r]);
		} return ret;
	}
};

int n, q;
vector<int> A, B, T;
vector<int> mp;
int flag[maxn], Now[maxn], It[maxn];
vector<int> ft[maxn];

void insert(int p, int val) {
	p++;
	for(; p <= q; p += p & -p)
		ft[p].push_back(val);
}
int query(int p, int x) {
	int ret = 0;
	for(; p > 0; p -= p & -p)
		ret += ft[p].end() - lower_bound(all(ft[p]), x);
	return ret;
}
int query(int l, int r, int val) {
	if(l >= r or l >= q or r >= q) return 0;
	return query(r + 1, val) - query(l, val);	
}

int32_t main () {
	// freopen("in", "r", stdin);

// input
	cin >> n >> q;
	A.resize(n), B.resize(n), T.resize(q);
	for(int i = 0; i < n; i++) {
		cin >> A[i] >> B[i];
		if(A[i] > B[i]) swap(A[i], B[i]), flag[i] = 1;
	}
	for(int &b : T) cin >> b;
// end
	
// compress
	for(int i = 0; i < n; i++) {
		mp.push_back(A[i]);
		mp.push_back(B[i]);
	}
	for(int b : T) mp.push_back(b);
	sort(all(mp));
	KeepUnique(mp);
	for(int i = 0; i < n; i++) {
		A[i] = lower_bound(all(mp), A[i]) - mp.begin();
		B[i] = lower_bound(all(mp), B[i]) - mp.begin();
	}
	for(int &b : T) {
		b = lower_bound(all(mp), b) - mp.begin();
	}
// end

	// for(int i = 0; i < n; i++) cout << A[i] << ' ' << B[i] << endl;
	// for(int b : T) cout << b << endl;

	MaxSegTree ds(mp.size() + 10);
	for(int i = 0; i < q; i++) {
		ds.update(T[i], i);
		insert(i, T[i]);
	}
	for(int i = 0; i <= q; i++) {
		sort(all(ft[i]));
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		if(A[i] == B[i]) {
			ans += mp[A[i]];
			continue;
		}
		int it = ds.query(A[i], B[i] - 1) + 1, now;
		if(!it) now = flag[i] ? B[i] : A[i];
		else now = B[i];
		Now[i] = now, It[i] = it;
		int tog = 0;
		for(int j = it; j < q; j++)
			if(T[j] >= B[i]) tog++;
		// cout << it << ' ' << tog << endl;
		if(tog & 1) now ^= A[i] ^ B[i];
		ans += mp[now];
	} cout << ans << endl;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int myrand(int, int)':
fortune_telling2.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
fortune_telling2.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~

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