Submission #1128551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128551		PagodePaiva	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1395 ms	103160 KiB

fortune_telling2

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6+10;

struct Segtree{
	int tree[4*N];
	int join(int a, int b){
		return max(a, b);
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] = val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr)); 
	}
} seg;

struct Segtree2{
	int tree[4*N];
	int join(int a, int b){
		return a+b;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] += val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr)); 
	}
} segsum;

vector <pair <int, int>> v;
int q[N];
map <int, int> m;
int tmm[N];
int res = 0;

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector <int> valores;
	for(int i = 1;i <= n;i++){
		int a, b;
		cin >> a >> b;
		v.push_back({a, b});
		valores.push_back(max(a, b)-1);
		valores.push_back(min(a, b));
		valores.push_back(max(a, b));
	}
	for(int i = 1;i <= k;i++){
		cin >> q[i];
		valores.push_back(q[i]);
	}
	sort(valores.begin(), valores.end());
	for(int i = 0;i < valores.size();i++){
		int vv = valores[i];
		m[vv] = i+1;
	}
	seg.build(1, 1, valores.size());
	for(int i = 1;i <= k;i++){
		//cout << q[i] << ' ' << m[q[i]] << endl;
		seg.update(1, 1, valores.size(), m[q[i]], i);
	}
	vector <pair <int, int>> queries;
	for(int i = 0;i < n;i++){
		int mx = max(v[i].first, v[i].second)-1;
		int mn = min(v[i].first, v[i].second);
		tmm[i] = seg.query(1, m[mn], m[mx], 1, valores.size());
		//cout << tmm[i] << ' ';
		if(tmm[i] > 0){
			v[i].first = mx+1;
			v[i].second = mn;
		}
		//cout << tmm[i] << ' ';
		queries.push_back({tmm[i], i});
	}
	//cout << endl;
	sort(queries.begin(), queries.end());
	segsum.build(1, 1, valores.size());
	for(int i = k;i >= 0;i--){
		while(!queries.empty()){
			if(queries.back().first != i) break;
			int pos = queries.back().second;
			int mx = max(v[pos].first, v[pos].second);
			int con = segsum.query(1, m[mx], valores.size(), 1, valores.size());
			//cout << pos << ' ' << con << endl;
			if(con%2 == 0) res += v[pos].first;
			else res += v[pos].second;
			queries.pop_back();
		}
		if(i == 0) break;
		segsum.update(1, 1, valores.size(), m[q[i]], 1);
	}
	cout << res << endl;
}

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