#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 2e5 + 5;
const int LG = 19;
int a[maxN],b[maxN],t[maxN];
int sp[LG][maxN],pre[maxN],suf[maxN];
int lg[maxN];
int n,k;
lli res;
void presp()
{
lg[1] = 0;
for (int i = 2;i <= n;++i) lg[i] = lg[i / 2] + 1;
for (int j = 1;j < LG;++j)
for (int i = 1;i <= n - (1 << j) + 1;++i)
sp[j][i] = min(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);
}
int get(int l,int r)
{
int k = lg[r - l + 1];
return min(sp[k][l],sp[k][r - (1 << k) + 1]);
}
void input()
{
cin >> n >> k;
for (int i = 1;i <= n;++i) cin >> a[i] >> b[i];
pre[0] = 0;
for (int i = 1;i <= k;++i)
{
cin >> t[i];
pre[i] = max(pre[i - 1],t[i]);
sp[0][i] = t[i];
}
suf[k + 1] = 0;
for (int i = k;i >= 1;--i) suf[i] = max(suf[i + 1],t[i]);
presp();
}
void solve()
{
for (int i = 1;i <= n;++i)
{
int mx = max(a[i],b[i]),mn = min(a[i],b[i]);
if (pre[k] < a[i]) res += a[i];
else if (pre[k] < b[i]) res += b[i];
else
{
int id,id1;
int l = 1,r = k;
while (l <= r)
{
int mid = (l + r) / 2;
if (pre[mid] >= mx)
{
l = mid + 1;
id = mid;
}
else r = mid - 1;
}
l = 1;r = id;
while (l <= r)
{
int mid = (l + r) / 2;
if (get(mid,id) >= mx)
{
r = mid - 1;
id1 = mid;
}
else l = mid + 1;
}
lli tmp;
if ((id - id1 + 1) % 2 == 0) tmp = mx;
else tmp = mn;
if (pre[id1 - 1] < mn && mn == a[i]) tmp = tmp ^ mx ^ mn;
if (suf[id + 1] >= mn) tmp = mx;
res += tmp;
//if (i == 1) cout << id1 << " " << id << "\n";
}
}
cout << res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("P1.inp","r",stdin);
//freopen("P1.out","w",stdout);
input();
solve();
}
Compilation message
fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:74:25: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | if (pre[id1 - 1] < mn && mn == a[i]) tmp = tmp ^ mx ^ mn;
| ~~~~^~~
fortune_telling2.cpp:72:21: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | if ((id - id1 + 1) % 2 == 0) tmp = mx;
| ~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
