#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 5;
vector<pair<int, int> > a(N);
vector<int> operations(N);
map<int, int> cc, revcc;
vector<int> segMax(N * 12), segCnt(N * 12);
void UpdateMax(int l, int r, int pos, int qpos, int qval) {
if(l == r) {
segMax[pos] = max(segMax[pos], qval);
return;
}
int mid = (l + r) >> 1;
if(mid >= qpos) {
UpdateMax(l, mid, pos * 2, qpos, qval);
}
else {
UpdateMax(mid + 1, r, pos * 2 + 1, qpos, qval);
}
segMax[pos] = max(segMax[pos * 2], segMax[pos * 2 + 1]);
}
int QueryMax(int l, int r, int pos, int ql, int qr) {
if(ql <= l && r <= qr)
return segMax[pos];
if(ql > r || l > qr)
return 0LL;
int mid = (l + r) >> 1;
return max(QueryMax(l, mid, pos * 2, ql, qr), QueryMax(mid + 1, r, pos * 2 + 1, ql, qr));
}
void UpdateCnt(int l, int r, int pos, int qpos) {
if(l == r) {
segCnt[pos]++;
return;
}
int mid = (l + r) >> 1;
if(mid >= qpos) {
UpdateCnt(l, mid, pos * 2, qpos);
}
else {
UpdateCnt(mid + 1, r, pos * 2 + 1, qpos);
}
segCnt[pos] = segCnt[pos * 2] + segCnt[pos * 2 + 1];
}
int QueryCnt(int l, int r, int pos, int ql, int qr) {
if(ql <= l && r <= qr) {
return segCnt[pos];
}
if(ql > r || l > qr)
return 0LL;
int mid = (l + r) >> 1;
return QueryCnt(l, mid, pos * 2, ql, qr) + QueryCnt(mid + 1, r, pos * 2 + 1, ql, qr);
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.second > b.second;
}
void Solve() {
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
cc[a[i].first]++;
cc[a[i].second]++;
}
for(int i = 1; i <= k; i++) {
cin >> operations[i];
cc[operations[i]]++;
}
int cnt = 1;
for(auto i: cc) {
cc[i.first] = cnt++;
revcc[cnt - 1] = i.first;
//cout << "Real value = " << i.first << ", coordinate compressed value = " << cnt - 1 << "\n";
//cout << "revcc[" << cnt - 1 << "]->" << i.first << "\n";
}
for(int i = 1; i <= n; i++) {
a[i].first = cc[a[i].first];
a[i].second = cc[a[i].second];
operations[i] = cc[operations[i]];
}
for(int i = 0; i < cnt * 4; i++) {
segMax[i] = 0;
segCnt[i] = 0;
}
for(int i = 1; i <= k; i++) {
UpdateMax(1, cnt - 1, 1, operations[i], i);
//UpdateCnt(1, cnt - 1, 1, operations[i]);
}
int ans = 0;
operations[0] = 0;
vector<pair<pair<int, int>, int> > temporary;
for(int i = 1; i <= n; i++) {
//cout << "i = " << i << ", a[i].first = " << a[i].first << ", a[i].second = " << a[i].second << "\n";
if(a[i].first == a[i].second) {
ans += revcc[a[i].first];
continue;
}
int lastPosition = QueryMax(1, cnt - 1, 1, min(a[i].first, a[i].second), max(a[i].first, a[i].second) - 1);
//cout << "Same as above -- lastPosition = " << lastPosition << "\n";
temporary.push_back(make_pair(a[i], lastPosition));
}
sort(temporary.begin(), temporary.end(), cmp);
int operationPos = k;
for(int i = 0; i < temporary.size(); i++) {
while(operationPos > temporary[i].second) {
UpdateCnt(1, cnt - 1, 1, operations[operationPos]);
operationPos--;
}
int numberofSwaps = QueryCnt(1, cnt - 1, 1, temporary[i].first.second, cnt - 1);
//cout << "numberofSwaps = " << numberofSwaps << " lastPosition = " << temporary[i].second << ", a[i] = {" << temporary[i].first.first << ", " << temporary[i].first.second << "}" << "\n";
if(temporary[i].second == 0) {
if(numberofSwaps % 2 == 0) {
ans += revcc[temporary[i].first.first];
}
else {
ans += revcc[temporary[i].first.second];
}
}
else {
//cout << "a[i] = {" << temporary[i].first.first << ", " << temporary[i].first.second << "}\n";
if(numberofSwaps % 2 == 0) {
ans += revcc[max(temporary[i].first.second, temporary[i].first.first)];
}
else {
ans += revcc[min(temporary[i].first.first, temporary[i].first.second)];
}
}
//cout << "ans = " << ans << "\n";
}
cout << ans << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void Solve()':
fortune_telling2.cpp:113:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < temporary.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
42700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
42700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
42700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
