#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];
int lg[maxN],id[maxN];
lli cnt[maxN],bit[maxN];
lli res;
int n,k;
vector<int> v;
vector<pair<int,int>> q;
void presp()
{
lg[1] = 0;
for (int i = 1;i <= k;++i) sp[0][i] = id[i];
for (int i = 2;i <= k;++i) lg[i] = lg[i / 2] + 1;
for (int j = 1;j < LG;++j)
for (int i = 1;i <= k - (1 << j) + 1;++i)
sp[j][i] = max(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);
}
int get(int l,int r)
{
int k = lg[r - l + 1];
return max(sp[k][l],sp[k][r - (1 << k) + 1]);
}
bool cmp(int x,int y)
{
if (t[x] == t[y]) return x > y;
return t[x] < t[y];
}
void input()
{
cin >> n >> k;
for (int i = 1;i <= n;++i) cin >> a[i] >> b[i];
for (int i = 1;i <= k;++i)
{
id[i] = i;
cin >> t[i];
}
sort(id + 1,id + k + 1,cmp);
presp();
}
bool cmp1(pair<int,int> x,pair<int,int> y)
{
return max(a[x.second],b[x.second]) > max(b[y.second],a[y.second]);
}
void update(int i,int val)
{
while (i <= k)
{
bit[i] += val;
i += (i & (-i));
}
}
lli getsum(int l,int r)
{
--l;
lli res = 0;
while (l > 0)
{
res -= bit[l];
l -= (l & (-l));
}
while (r > 0)
{
res += bit[r];
r -= (r & (-r));
}
return res;
}
void solve()
{
for (int i = 1;i <= n;++i)
{
int mn = min(a[i],b[i]);
int mx = max(a[i],b[i]);
int l = 1,r = k,id1 = 0,id2 = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (t[id[mid]] >= mn)
{
id1 = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 1;r = k;
while (l <= r)
{
int mid = (l + r) / 2;
if (t[id[mid]] < mx)
{
id2 = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (id1 > id2 || id1 == 0 || id2 == 0) q.push_back({0,i});
else q.push_back({get(id1,id2),i});
}
sort(q.begin(),q.end(),cmp1);
int it = k;
lli ans = 0;
for (int i = 0;i < q.size();++i)
{
while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1) update(id[it],1);--it;
res = getsum(q[i].first + 1,k);
if (q[i].first == 0 && b[q[i].second] > a[q[i].second]) res--;
if (res % 2 == 0) ans += max(b[q[i].second],a[q[i].second]);
else ans += min(b[q[i].second],a[q[i].second]);
}
cout << ans;
}
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:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i = 0;i < q.size();++i)
| ~~^~~~~~~~~~
fortune_telling2.cpp:109:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
109 | while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1) update(id[it],1);--it;
| ^~~~~
fortune_telling2.cpp:109:93: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
109 | while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1) update(id[it],1);--it;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
12624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
12624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
12624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
