Submission #377517

#	Time	Username	Problem	Language	Result	Execution time	Memory
377517		reymontada61	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	3 ms	1004 KiB

fortune_telling2

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

int n, k, ans;
vector<pair<pair<int, int>, int>> crs; 
vector<pair<int, int>> qs;

const int MXN = 200005;

int seg[MXN * 4];
int arr[MXN];

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = qs[l].second;
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return -1;
	int m = (l + r) / 2;
	return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
}

struct wavelet_tree{
	#define vi vector<int>
	#define pb push_back
	int lo, hi;
	wavelet_tree *l, *r;
	vi b;
 
	//nos are in range [x,y]
	//array indices are [from, to)
	wavelet_tree(int *from, int *to, int x, int y){
		lo = x, hi = y;
		if(lo == hi or from >= to) return;
		int mid = (lo+hi)/2;
		auto f = [mid](int x){
			return x <= mid;
		};
		b.reserve(to-from+1);
		b.pb(0);
		for(auto it = from; it != to; it++)
			b.pb(b.back() + f(*it));
		//see how lambda function is used here	
		auto pivot = stable_partition(from, to, f);
		l = new wavelet_tree(from, pivot, lo, mid);
		r = new wavelet_tree(pivot, to, mid+1, hi);
	}
 
	//kth smallest element in [l, r]
	int kth(int l, int r, int k){
		if(l > r) return 0;
		if(lo == hi) return lo;
		int inLeft = b[r] - b[l-1];
		int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left 
		int rb = b[r]; //amt of nos in first (r) nos that go in left
		if(k <= inLeft) return this->l->kth(lb+1, rb , k);
		return this->r->kth(l-lb, r-rb, k-inLeft);
	}
 
	//count of nos in [l, r] Less than or equal to k
	int LTE(int l, int r, int k) {
		if(l > r or k < lo) return 0;
		if(hi <= k) return r - l + 1;
		int lb = b[l-1], rb = b[r];
		return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
	}
 
	//count of nos in [l, r] equal to k
	int count(int l, int r, int k) {
		if(l > r or k < lo or k > hi) return 0;
		if(lo == hi) return r - l + 1;
		int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
		if(k <= mid) return this->l->count(lb+1, rb, k);
		return this->r->count(l-lb, r-rb, k);
	}
	~wavelet_tree(){
		delete l;
		delete r;
	}
};

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> k;
	for (int i=0; i<n; i++) {
		int a, b;
		cin >> a >> b;
		
		if (a == b) {
			ans += a;
			continue;
		}
		
		int s = 0;
		if (a > b) {
			swap(a, b); s = 1;
		}
		
		crs.push_back({{a, b}, s});
		
	}
	
	n = crs.size();
	
	for (int i=0; i<k; i++) {
		int x;
		cin >> x;
		qs.push_back({x, i});
	}
	
	sort(qs.begin(), qs.end());
	
	for (int x=0; x<k; x++) {
		arr[x] = qs[x].second;
	}
	
	build(1, 0, k-1);
	wavelet_tree tr(arr, arr+k, 0, k);
	
	
	for (auto x: crs) {
		int a = x.first.first, b = x.first.second;
		
		int e = lower_bound(qs.begin(), qs.end(), make_pair(a, 0ll)) - qs.begin();
		int f = upper_bound(qs.begin(), qs.end(), make_pair(b-1, k)) - qs.begin() - 1;
		
		int ls = query(1, 0, k-1, e, f);
		
		int up = x.second;
		if (ls != -1) up = 1;
		
		int flips = ((k-1)-(f+1)+1) - tr.LTE(f+1, k-1, ls);
		
		for (int j=f+1; j<qs.size(); j++) {
			if (qs[j].second > ls) flips++;
		}
		
		if (flips % 2 == 1) up = 1 - up;
		
		if (up) ans += b;
		else ans += a;
		
	}
	
	cout << ans << endl;

}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:145:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for (int j=f+1; j<qs.size(); j++) {
      |                   ~^~~~~~~~~~

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