oj.uz

Submission #519260

# Submission time Handle Problem Language Result Execution time Memory
519260 2022-01-26T06:25:32 Z amunduzbaev Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 3 ms 3552 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e5 + 5;
int a[N], b[N], f[N], t[N];
struct ST{
	int tree[N<<2], sum[N<<2];
	
	void init(){
		memset(tree, 127, sizeof tree);
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v, sum[x] = 1; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		sum[x] = sum[x<<1] + sum[x<<1|1];
	}
	
	int get(int a, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return lx;
		int m = (lx + rx) >> 1;
		if(tree[x<<1] < a) return get(a, m+1, rx, x<<1|1);
		return get(a, lx, m, x<<1);
	}
	
	int get_s(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return sum[x];
		int m = (lx + rx) >> 1;
		return get_s(l, r, lx, m, x<<1) + get_s(l, r, m+1, rx, x<<1|1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	tree.init();
	int n, k; cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		if(a[i] > b[i]) f[i] = 1, swap(a[i], b[i]);
	}
	
	for(int i=0;i<k;i++){
		cin>>t[i];
	}
	
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j) { return (a[i] > a[j]); });
	vector<int> q(k); iota(q.begin(), q.end(), 0);
	sort(q.begin(), q.end(), [&](int i, int j) { return (t[i] > t[j]); });
	int j = 0;
	long long res = 0;
	for(auto i : p){
		while(j<k && t[q[j]] >= a[i]){
			tree.sett(q[j], t[q[j]]);
			j++;
		}
		
		int p = tree.get(b[i]);
		if(a[i] <= t[p] && t[p] < b[i]){
			int s = tree.get_s(p + 1, N);
			if(s&1) res += a[i];
			else res += b[i];
		} else {
			if(f[i]) swap(a[i], b[i]);
			if(j&1){
				res += b[i];
			} else {
				res += a[i];
			}
		}
	}
	
	cout<<res<<"\n";
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3552 KB Output isn't correct
2 Halted 0 ms 0 KB -