oj.uz

Submission #289613

# Submission time Handle Problem Language Result Execution time Memory
289613 2020-09-02T19:04:14 Z ngotienhung Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 158 ms 11940 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define ff first
#define ss second

using namespace std;

const int maxN = 2e5 + 5;
const int inf = 1e9;

int a[maxN], b[maxN], t[maxN], st[maxN * 4], fen[maxN], n, k, sz;
vector<int> q[maxN];

void update(int v, int l, int r, int idx, int x)
{
	if(l > idx || r < idx)
        return;

	if(l == idx && r == idx){
		st[v] = x;
		return;
	}

	int mid = (l + r) / 2;
	update(v * 2, l, mid, idx, x);
	update(v * 2 + 1, mid + 1, r, idx, x);
	st[v] = max(st[v * 2], st[v * 2 + 1]);
}

int query(int v, int l, int r, int ql, int qr)
{
	if(l > qr || r < ql)
        return 0;
	if(l >= ql && r <= qr)
        return st[v];
	int mid = (l + r) / 2;
	return max(query(v * 2, l, mid, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}

void add(int i){
	if(!i) return;
	while(i <= sz){
		fen[i]++;
		i += (i & (-i));
    }
}

int sum(int i){
	int res = 0;
	while(i > 0){
		res += fen[i];
		i -= (i & (-i));
	}
	return res;
}

int rangesum(int l, int r){
	return sum(r) - sum(l - 1);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;

	vector<int> v;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		v.pb(a[i]);
		v.pb(b[i]);
	}
	for(int i = 1; i <= k; i++){
		cin >> t[i];
		v.pb(t[i]);
	}

	sort(v.begin(), v.end());
	v.resize(distance(v.begin(), unique(v.begin(), v.end())));
	sz = v.size();

	for(int i = 1; i <= k; i++){
		t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin() + 1;
		update(1, 1, v.size(), t[i], i);
	}

	ll res = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] == b[i]){
			res += a[i];
			continue;
		}
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
		b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
		int mx = query(1, 1, v.size(), min(a[i], b[i]), max(a[i], b[i]) - 1);
		if(mx && a[i] < b[i])
            swap(a[i], b[i]);
		q[mx].pb(i);
	}

	for(int i = k; i >= 0; --i){
		for(auto x : q[i]){
			int cnt = sum(sz) - sum(max(a[x], b[x]) - 1);
			if(cnt & 1)
				swap(a[x], b[x]);
			res += v[a[x] - 1];
		}
		add(t[i]);
	}

	cout << res << endl;
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 5 ms 5120 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 5 ms 5120 KB Output is correct
12 Correct 5 ms 5120 KB Output is correct
13 Correct 5 ms 5120 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 5 ms 5120 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 5 ms 5120 KB Output is correct
12 Correct 5 ms 5120 KB Output is correct
13 Correct 5 ms 5120 KB Output is correct
14 Correct 19 ms 6144 KB Output is correct
15 Correct 40 ms 7032 KB Output is correct
16 Correct 59 ms 8228 KB Output is correct
17 Correct 79 ms 8948 KB Output is correct
18 Correct 78 ms 8948 KB Output is correct
19 Correct 77 ms 8948 KB Output is correct
20 Correct 76 ms 9064 KB Output is correct
21 Correct 77 ms 9076 KB Output is correct
22 Correct 59 ms 8308 KB Output is correct
23 Correct 61 ms 7796 KB Output is correct
24 Correct 56 ms 7668 KB Output is correct
25 Correct 61 ms 8564 KB Output is correct
26 Correct 58 ms 8436 KB Output is correct
27 Correct 69 ms 8784 KB Output is correct
28 Correct 61 ms 8824 KB Output is correct
29 Correct 69 ms 8948 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 5 ms 5120 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 5 ms 5120 KB Output is correct
12 Correct 5 ms 5120 KB Output is correct
13 Correct 5 ms 5120 KB Output is correct
14 Correct 19 ms 6144 KB Output is correct
15 Correct 40 ms 7032 KB Output is correct
16 Correct 59 ms 8228 KB Output is correct
17 Correct 79 ms 8948 KB Output is correct
18 Correct 78 ms 8948 KB Output is correct
19 Correct 77 ms 8948 KB Output is correct
20 Correct 76 ms 9064 KB Output is correct
21 Correct 77 ms 9076 KB Output is correct
22 Correct 59 ms 8308 KB Output is correct
23 Correct 61 ms 7796 KB Output is correct
24 Correct 56 ms 7668 KB Output is correct
25 Correct 61 ms 8564 KB Output is correct
26 Correct 58 ms 8436 KB Output is correct
27 Correct 69 ms 8784 KB Output is correct
28 Correct 61 ms 8824 KB Output is correct
29 Correct 69 ms 8948 KB Output is correct
30 Incorrect 158 ms 11940 KB Output isn't correct
31 Halted 0 ms 0 KB -