#undef KEV
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 200010, SQ = 600;
int a[MAX_N], b[MAX_N], mt[MAX_N], n, m;
struct ASK {
int a, b, c, d;
}qry[MAX_N];
bool operator < (ASK a, ASK b) {
int l1 = a.c, r1 = a.d;
int l2 = b.c, r2 = b.d;
int aid = l1 / SQ, bid = l2 / SQ;
if (aid != bid) return aid < bid;
return (r1 < r2) ^ (aid & 1);
}
pair<int,int> lisan[MAX_N];
struct DS {
int sum[SQ], cnt[MAX_N], all;
void add(int i, int d) {
sum[i / SQ] += d;
cnt[i] += d;
all += d;
}
int find_mx() {
int id = n / SQ;
int RB = id * SQ;
for (int i = n;i >= RB;--i)
if (cnt[i]) return i;
for (int i = id - 1;i >= 0;--i)
if (sum[i]) for (int j = (i * SQ) - 1;;--j)
if (cnt[j]) return j;
return 0;
}
int getsum(int l, int r) {
assert(r == n);
int res = all;
--l;
int lid = l / SQ;
for (int i = 0;i < lid;++i) res += sum[i];
for (int i = lid * SQ;i <= l;++i) res += cnt[i];
return res;
}
}RMQ[3];
int sum[MAX_N];
array<int, 3> getnxt() {
int p = RMQ[1].find_mx();
array<int, 3> res;
int v = RMQ[2].getsum(p, n) & 1;
if (p) {
if (v == 1) return {-1, 1, 1};
else return {-1, 2, 2};
}
if (v == 1) return {-1, 2, 1};
else return {-1, 1, 2};
}
ll solveall() {
sort(qry, qry + n);
ll res = 0;
auto addin = [&](int pos, int d) {
int rp = lisan[pos].second;
if (sum[pos]) RMQ[ sum[pos] ].add(rp, -1);
sum[pos] += d;
if (sum[pos]) RMQ[ sum[pos] ].add(rp, 1);
//tree.modi(lisan[pos].second, sum[pos]);
};
int cl = m, cr = m;
for (int i = 0;i < n;++i) {
auto [a, b, l, r] = qry[i];
while (cl > l) addin(--cl, 1);
while (cr > r) addin(--cr, 1);
while (cr < r) addin(cr++,-1);
while (cl < l) addin(cl++,-1);
auto ret = getnxt();
ll ans ;
if (a <= b) ans = ret[1] == 1 ? min(a, b) : max(a, b);
else ans = ret[2] == 1 ? min(a, b) : max(a, b);
res += ans;
}
return res;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0;i < n;++i)
cin >> a[i] >> b[i];
for (int i = 0;i < m;++i) {
cin >> mt[i];
lisan[i] = {mt[i], i};
}
sort(lisan, lisan + m);
for (int i = 0;i < n;++i) {
int c = a[i], d = b[i];
if (c > d) swap(c, d);
c = lower_bound(lisan, lisan + m, make_pair(c, -1)) - lisan;
d = lower_bound(lisan, lisan + m, make_pair(d, -1)) - lisan;
qry[i] = {a[i], b[i], c, d};
}
cout << solveall() << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'std::array<int, 3> getnxt()':
fortune_telling2.cpp:67:16: warning: unused variable 'res' [-Wunused-variable]
67 | array<int, 3> res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
