This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = int(2e5) + 3;
const int M = int(6e5) + 3;
vector<int> v, c[N];
int n, m, a[N], b[N], t[N], p[N];
int l[M << 2], h[M << 2], st[M << 2];
void Build(int x, int low, int high) {
l[x] = low, h[x] = high;
if(l[x] == h[x]) {
st[x] = p[l[x]];
return;
}
int mid = (low + high) >> 1;
Build(x << 1, low, mid);
Build(x << 1 | 1, mid + 1, high);
st[x] = max(st[x << 1], st[x << 1 | 1]);
}
int Query(int x, int low, int high) {
if(high < low) return -1;
if(l[x] > high || h[x] < low) return -1;
if(l[x] >= low && h[x] <= high) return st[x];
return max(Query(x << 1, low, high), Query(x << 1 | 1, low, high));
}
int Pos(int x) {return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;}
void Update(int x) {
for(; x > 0; x -= (x & -x)) ++l[x];
}
int Get(int x) {
int res = 0;
for(; x <= int(v.size()); x += (x & -x)) res += l[x];
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin >> n >> m;
for(int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
v.pb(a[i]), v.pb(b[i]);
}
for(int i = 0; i < m; ++i) cin >> t[i], v.pb(t[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
memset(&p, -1, sizeof p);
for(int i = 0; i < m; ++i) p[t[i] = Pos(t[i])] = i;
Build(1, 1, int(v.size()));
for(int i = 0; i < n; ++i) {
a[i] = Pos(a[i]), b[i] = Pos(b[i]);
c[Query(1, min(a[i], b[i]), max(a[i], b[i]) - 1) + 1].pb(i);
}
fill(l, l + int(v.size()) + 1, 0);
long long res = 0;
for(int i = m; i >= 0; --i) {
if(i - m) Update(t[i]);
for(int id: c[i]) {
h[id] = Get(max(a[id], b[id]));
if(i == 0 && a[id] < b[id]) ++h[id];
if(h[id] & 1) res += v[min(a[id], b[id]) - 1];
else res += v[max(a[id], b[id]) - 1];
}
}
cout << res;
}
Compilation message (stderr)
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |