#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 200005, L = 524288;
int n, q, a[N], b[N], c[N], lst[N], cnt[N];
long long ans;
vector<int> cpr;
vector<pii> swp[N];
struct maxseg {
int v[2*L];
void upd (int P, int V) {
P += L;
while(P) {
v[P] = max(v[P], V);
P /= 2;
}
}
int get (int S, int E) {
S += L; E += L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R = max(R, v[S++]);
if(E%2 == 0) R = max(R, v[E--]);
S /= 2; E /= 2;
}
return R;
}
} seg1;
struct sumseg {
int v[2*L];
void upd (int P, int V) {
P += L;
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int S, int E) {
S += L; E += L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++];
if(E%2 == 0) R += v[E--];
S /= 2; E /= 2;
}
return R;
}
} seg2;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i],&b[i]);
cpr.push_back(a[i]);
cpr.push_back(b[i]);
}
sort(cpr.begin(), cpr.end());
cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
for(int i=1;i<=n;i++) {
a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin();
b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin();
}
for(int i=1;i<=q;i++) {
scanf("%d", &c[i]);
c[i] = lower_bound(cpr.begin(), cpr.end(), c[i]) - cpr.begin();
seg1.upd(c[i], i);
}
for(int i=1;i<=n;i++) {
lst[i] = seg1.get(min(a[i], b[i]), max(a[i], b[i])-1);
swp[lst[i]+1].push_back({max(a[i], b[i]), i});
}
for(int i=q;i>=1;i--) {
seg2.upd(c[i], 1);
for(auto &T : swp[i]) {
int A, B;
tie(A, B) = T;
cnt[B] += seg2.get(A, L-1);
}
}
for(int i=1;i<=n;i++) {
int X = (lst[i] && a[i] < b[i]) + cnt[i];
ans += cpr[X % 2 ? b[i] : a[i]];
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i],&b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c[i]);
~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
