/*input
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
cout << x.fi << sp << x.se << sp;
return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
return os;
}
struct data {
int fi, se, state;
data(int _fi, int _se, int _state): fi(_fi), se(_se), state(_state) {};
};
bool bySE(data x, data y) {
return x.se < y.se;
}
int n, q;
vector<data> a;
vector<pair<int, int> > b;
array<int, N> tree;
array<array<int, 20>, N> rmq;
array<int, N> lg2;
void update(int i, int val) {
for (; i; i -= i & -i) tree[i] += val;
}
int get(int i) {
int ret = 0;
for (; i <= n; i += i & -i) ret += tree[i];
return ret;
}
void initRMQ() {
for (int i = 1; i < N; i++) lg2[i] = log2(i);
for (int i = 1; i <= q; i++)
rmq[i][0] = b[i - 1].se;
for (int k = 1; k < 20; k++) {
for (int i = 1; i + (1 << k) - 1 <= q; i++) {
rmq[i][k] = max(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
}
}
}
int getRMQ(int l, int r) {
if (l > r) return -1;
int len = lg2[r - l + 1];
return max(rmq[l][len], rmq[r - (1 << len) + 1][len]);
}
void solve() {
int it = b.size() - 1;
int ans = 0;
for (int i = (signed)a.size() - 1; i >= 0; i--) {
while (it >= 0 && b[it].fi >= a[i].se) {
update(b[it].se, 1);
it--;
}
if (a[i].fi == a[i].se) {
ans += a[i].fi;
continue;
}
int l = lower_bound(b.begin(), b.end(), mp(a[i].fi, -1LL)) - b.begin();
int r = (signed)(upper_bound(b.begin(), b.end(), mp(a[i].se, -1LL)) - b.begin()) - 1;
int rec = getRMQ(l + 1, r + 1);
if (rec == -1) {
if (a[i].state == 1) ans += a[i].se;
else ans += a[i].fi;
continue;
}
a[i].state = 1;
rec++;
rec = get(rec);
if (rec % 2) a[i].state = 0;
if (a[i].state == 1) ans += a[i].se;
else ans += a[i].fi;
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
if (x < y) a.push_back(data(x, y, 0));
else a.push_back(data(y, x, 1));
}
sort(a.begin(), a.end(), bySE);
for (int i = 1; i <= q; i++) {
int t; cin >> t;
b.push_back(mp(t, i));
}
sort(b.begin(), b.end());
initRMQ();
solve();
}
Compilation message
fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
fortune_telling2.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
^
fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
fortune_telling2.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
37508 KB |
Output is correct |
| 2 |
Correct |
29 ms |
38404 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
38404 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
43400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
