#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 = 550;
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 node {
int nxt[3];
node (int val = 0) {
if (val == 0) {
nxt[1] = 1;
nxt[2] = 2;
}
if (val == 1) {
nxt[1] = 2;
nxt[2] = 2;
}
if (val == 2) {
nxt[1] = 2;
nxt[2] = 1;
}
}
node (node a, node b) {
for (int i = 1;i <= 2;++i)
nxt[i] = b.nxt[ a.nxt[i] ];
}
};
struct sgt {
vector<node> v;
int n;
sgt (int _n) : n(_n) {
v.resize(n<<1);
}
void modi(int i, int val) {
i += n;
v[i] = node(val);
for (;i>>=1;)
update(i);
}
void update(int i) {
v[i] = node(v[i<<1], v[i<<1|1]);
}
node qry(int l, int r) {
l += n, r += n;
node lres(0), rres(0);
for (;l < r;l>>=1, r>>=1) {
if (l&1) lres = node(lres, v[l++]);
if (r&1) rres = node(v[--r], rres);
}
return node(lres, rres);
}
};
int sum[MAX_N];
int brute(int a, int b) {
for (int i = 0;i < m;++i)
if (a <= mt[i]) swap(a, b);
return a;
}
ll solveall() {
sort(qry, qry + n);
ll res = 0;
sgt tree(m);
auto addin = [&](int pos, int d) {
sum[pos] += d;
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 = tree.qry(0, m);
ll ans ;
if (a <= b) ans = ret.nxt[1] == 1 ? min(a, b) : max(a, b);
else ans = ret.nxt[2] == 1 ? min(a, b) : max(a, b);
DE(a, b, ans, brute(a, b));
debug(sum, sum + m);
DE(ret.nxt[1], ret.nxt[2]);
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 'll solveall()':
fortune_telling2.cpp:16:17: warning: statement has no effect [-Wunused-value]
16 | #define DE(...) 0
| ^
fortune_telling2.cpp:115:3: note: in expansion of macro 'DE'
115 | DE(a, b, ans, brute(a, b));
| ^~
fortune_telling2.cpp:17:20: warning: statement has no effect [-Wunused-value]
17 | #define debug(...) 0
| ^
fortune_telling2.cpp:116:3: note: in expansion of macro 'debug'
116 | debug(sum, sum + m);
| ^~~~~
fortune_telling2.cpp:16:17: warning: statement has no effect [-Wunused-value]
16 | #define DE(...) 0
| ^
fortune_telling2.cpp:117:3: note: in expansion of macro 'DE'
117 | DE(ret.nxt[1], ret.nxt[2]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
7 ms |
492 KB |
Output is correct |
| 3 |
Correct |
12 ms |
492 KB |
Output is correct |
| 4 |
Correct |
12 ms |
492 KB |
Output is correct |
| 5 |
Correct |
13 ms |
492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
640 KB |
Output is correct |
| 8 |
Correct |
4 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
3564 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
7 ms |
492 KB |
Output is correct |
| 3 |
Correct |
12 ms |
492 KB |
Output is correct |
| 4 |
Correct |
12 ms |
492 KB |
Output is correct |
| 5 |
Correct |
13 ms |
492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
640 KB |
Output is correct |
| 8 |
Correct |
4 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
3564 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
7 ms |
492 KB |
Output is correct |
| 3 |
Correct |
12 ms |
492 KB |
Output is correct |
| 4 |
Correct |
12 ms |
492 KB |
Output is correct |
| 5 |
Correct |
13 ms |
492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
640 KB |
Output is correct |
| 8 |
Correct |
4 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
3564 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
