#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)
using namespace std;
typedef long long ll;
const int N = 200002;
struct data{
int x, id;
bool operator <(data g){
return x < g.x;
}
} a[N], b[N];
int n, k, pos[N], ans[N], h3[N], h4[N];
pair <int, int> h1[N], h2[N];
vector <vector <int> > t1, t2;
void up(int x, int i, int id){
for(x; x > 0; x -= (x & -x)){
if(id==1){
if(i > h1[x].first){
h1[x].second = h1[x].first;
h1[x].first = i;
}
else if(i == h1[x].first){
h1[x].second = i;
}
else{
if(i > h1[x].second){
h1[x].second = i;
}
}
h3[x] = min(h3[x], i);
}
else{
if(i > h2[x].first){
h2[x].second = h2[x].first;
h2[x].first = i;
}
else if(i == h2[x].first){
h2[x].second = i;
}
else{
if(i > h2[x].second){
h2[x].second = i;
}
}
h3[x] = min(h4[x], i);
}
}
}
int get1(int x, int id){
int res = 0;
for(x; x <= n; x += (x & -x)){
if(id==1) res = max(res, h1[x].first);
else res = max(res, h2[x].first);
}
return res;
}
int get2(int x, int y){
int res = 0;
for(x; x <= n; x += (x & -x)){
if(h2[x].first < y) res = max(res, h2[x].first);
if(h2[x].second < y) res = max(res, h2[x].second);
}
return res;
}
int get3(int x){
int res = 1e9;
for(x; x <= n; x += (x & -x)) res = min(res, h3[x]);
return res;
}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> k;
t1.resize(n + 1); t2.resize(n + 1);
memset(h3, 0x3f3f3f, sizeof(h3));
memset(h4, 0x3f3f3f, sizeof(h4));
f1(i, n){
cin >> a[i].x >> b[i].x;
b[i].id = a[i].id = i;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
f1(i, k){
int x; cin >> x;
data g = {x + 1, 0};
int ki = lower_bound(a + 1, a + n + 1, g) - a; --ki;
t1[ki].push_back(i);
ki = lower_bound(b + 1, b + n + 1, g) - b; --ki;
t2[ki].push_back(i);
}
for(int i = n; i >= 1; i--){
for(auto x:t1[i]){
up(i, x, 1);
}
for(auto x:t2[i]){
up(i, x, 2);
}
}
f1(i, n){
pos[b[i].id] = i;
}
f1(i, n){
int k = a[i].id;
int u = get1(i, 1);
if(u==0) ans[k] = 1;
else{
int v = get1(pos[k], 2);
if(v > u) ans[k] = 1;
else if(v==u){
int tr = get2(pos[k], v);
if(tr > N) tr = 0;
int rt = get3(i);
if(tr==0){
ans[k] = 2;
continue;
}
if(rt==u){
ans[k] = 2;
continue;
}
if(tr > rt && tr < u){
ans[k] = 2;
continue;
}
ans[k] = 1;
}
else{
ans[k] = 2;
}
}
}
ll res = 0;
f1(i, n){
if(ans[a[i].id]==1){
res += ll(a[i].x);
}
else{
res += ll(b[pos[a[i].id]].x);
}
}
cout << res;
}
Compilation message
fortune_telling2.cpp: In function 'void up(int, int, int)':
fortune_telling2.cpp:20:10: warning: statement has no effect [-Wunused-value]
for(x; x > 0; x -= (x & -x)){
^
fortune_telling2.cpp: In function 'int get1(int, int)':
fortune_telling2.cpp:56:10: warning: statement has no effect [-Wunused-value]
for(x; x <= n; x += (x & -x)){
^
fortune_telling2.cpp: In function 'int get2(int, int)':
fortune_telling2.cpp:65:10: warning: statement has no effect [-Wunused-value]
for(x; x <= n; x += (x & -x)){
^
fortune_telling2.cpp: In function 'int get3(int)':
fortune_telling2.cpp:74:10: warning: statement has no effect [-Wunused-value]
for(x; x <= n; x += (x & -x)) res = min(res, h3[x]);
^
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
130 ms |
5688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
