#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair < int , int >
#define pb push_back
#define eb emplace_back
using namespace std;
int f[200010][20] , BIT[200010] , c[200010];
ii a[200010];
void upl(int x) {
for ( ; x > 0 ; x -= (-x & x))
BIT[x]++;
}
int dwl(int x) {
int tmp = 0;
for ( ; x <= 200000 ; x += (-x & x))
tmp += BIT[x];
return tmp;
}
int get(int l,int r) {
int k = __lg(r - l + 1);
return max(f[l][k] , f[r - (1 << k) + 1][k]);
}
int main() {
freopen("JOI14.INP","r",stdin);
freopen("JOI14.OUT","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n , k;
cin >> n >> k;
vector < int > vc;
vector < ii > cat;
for (int i = 1 ; i <= n ; ++i) cin >> a[i].fi >> a[i].se;
for (int i = 1 ; i <= k ; ++i) {
cin >> c[i];
vc.pb(c[i]);
}
sort(vc.begin(),vc.end());
for (int i = 1 ; i <= k ; ++i) {
c[i] = lower_bound(vc.begin() , vc.end() , c[i]) - vc.begin() + 1;
f[c[i]][0] = i;
}
int l = __lg(k);
for (int j = 1 ; j <= l ; ++j)
for (int i = 1 ; i + (1 << j) - 1 <= k ; ++i)
f[i][j] = max(f[i][j - 1] , f[i + (1 << (j - 1))][j - 1]);
for (int i = 1 ; i <= n ; ++i) {
int l = lower_bound(vc.begin() , vc.end() , min(a[i].fi , a[i].se)) - vc.begin() + 1;
int r = lower_bound(vc.begin() , vc.end() , max(a[i].fi , a[i].se)) - vc.begin();
//cout << l << ' ' << r << '\n';
cat.eb(get(l , r) , i);
}
sort(cat.begin(),cat.end());
int cur = 1;
long long ans = 0;
for (auto v : cat) {
while (cur <= v.fi) upl(c[cur]) , cur++;
int ma = max(a[v.se].fi , a[v.se].se);
int res = k - (lower_bound(vc.begin() , vc.end() , ma) - vc.begin());
ma = lower_bound(vc.begin() , vc.end() , ma) - vc.begin() + 1;
res -= dwl(ma);
if (v.fi) ans += ((a[v.se].fi < a[v.se].se) ^ (res & 1) ? a[v.se].se : a[v.se].fi);
else ans += (res & 1 ? a[v.se].se : a[v.se].fi);
}
cout << ans;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
31 | freopen("JOI14.INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
32 | freopen("JOI14.OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
1528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
1528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
1528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
