#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int N = 2e5 + 2, NN = 2e6 + 2;
ll a[N], b[N], t[N], A[N], B[N], T[N], S[NN], ST[NN];
vector < ll > V[N];
bool Changed[N] = {false};
map < int , int > M;
ll mid;
void Update(ll p, ll lo, ll hi, ll ind, ll x) {
if ( lo == hi) {
// cout << lo << " " << hi << " " << ind << endl;
S[p] = x;
return ;
}
mid = (lo + hi)/2;
if ( ind <= mid) Update(2 * p, lo, mid, ind, x);
else Update(2 * p + 1, mid + 1, hi, ind, x);
S[p]= max(S[2 * p], S[2 *p + 1]);
}
ll Find(ll p, ll lo, ll hi, ll l, ll r) {
// cout << lo << " " << hi << " " << l << " " << r << endl;
if ( l > r) return 0;
if ( lo >= l && hi <= r) return S[p];
if ( hi < l || lo > r) return 0;
mid = (lo + hi)/2;
if ( l== 3 && r == 6 ) cout << lo << " " << hi << " " << max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r)) << endl;
return max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r));
}
void update(ll p, ll lo, ll hi, ll ind) {
if ( lo == hi) {
ST[p] ++;
return ;
}
mid = (lo + hi)/2;
if ( ind <= mid) update(2 * p, lo, mid, ind);
else update(2 * p + 1, mid + 1, hi, ind);
ST[p]= ST[2 * p] +ST[2 *p + 1];
}
ll find(ll p, ll lo, ll hi, ll l, ll r) {
if ( lo >= l && hi <= r) return ST[p];
if ( hi < l || lo > r) return 0;
mid = (lo + hi)/2;
return find(2 * p, lo, mid, l, r) + find(2 * p + 1, mid + 1, hi, l, r);
}
int main() {
// freopen("moocast.in", "r", stdin);
// freopen("moocast.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, ans, s, sum, x, y, r, p, i, j;
cin >> n >> m;
vector < pair < ll, pair < ll, ll > > > v;
for (i = 1; i <= n; i ++) {
cin >> a[i] >> b[i];
if ( a[i] > b[i]) {
swap(a[i], b[i]);
Changed[i] = 1;
}
v.push_back({a[i], {i, 1}});
v.push_back({b[i], {i, 2}});
}
for (i = 1; i <= m; i++){
cin >> t[i];
v.push_back({t[i], {i, 3}});
}
sort(v.begin(), v.end());
r = 1;
for (i = 0; i < v.size(); i ++) {
if ( M[v[i].first] == 0) {
M[v[i].first] = r;
r ++;
}
if ( v[i].second.second == 1) {
A[v[i].second.first] = M[v[i].first];
}
if ( v[i].second.second == 2) {
B[v[i].second.first] = M[v[i].first];
}
if ( v[i].second.second == 3) {
T[v[i].second.first] = M[v[i].first];
}
}
for (i = 1; i <= m; i ++) {
Update(1, 1, 6e5, T[i], i);
}
for (i = 1; i <= n; i ++) {
// cout << A[i] << " " << B[i] << endl << endl;
s = Find(1, 1, 6e5, A[i], B[i] - 1);
// cout << s << endl << endl;
V[s].push_back(i);
}
ll Ans[N];
sum =0;
for (i = m; i >= 0; i --) {
for (j = 0; j < V[i].size(); j ++) {
r = V[i][j];
Ans[r]= find(1, 1, NN, B[r], NN);
// cout << r << " " << Ans[r] << " " << i << endl;
if ( Ans[r] % 2 == 0) {
if ( i == 0 && Changed[r]) sum += b[r];
else sum += a[r];
}
else {
if ( i == 0 && Changed[r]) sum += b[r];
else sum += a[r];
}
}
if (i == 0) continue;
update(1, 1, NN, t[i]);
}
cout << sum << endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:76:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
fortune_telling2.cpp:104:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (j = 0; j < V[i].size(); j ++) {
| ~~^~~~~~~~~~~~~
fortune_telling2.cpp:54:11: warning: unused variable 'ans' [-Wunused-variable]
54 | ll n, m, ans, s, sum, x, y, r, p, i, j;
| ^~~
fortune_telling2.cpp:54:24: warning: unused variable 'x' [-Wunused-variable]
54 | ll n, m, ans, s, sum, x, y, r, p, i, j;
| ^
fortune_telling2.cpp:54:27: warning: unused variable 'y' [-Wunused-variable]
54 | ll n, m, ans, s, sum, x, y, r, p, i, j;
| ^
fortune_telling2.cpp:54:33: warning: unused variable 'p' [-Wunused-variable]
54 | ll n, m, ans, s, sum, x, y, r, p, i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
31308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
31308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
31308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
