This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int lsb(int x){
return x & -x;
}
const int NMAX = 1e6 + 1;
vector <int> bit(NMAX);
int n;
void add(int v, int val){
while(v < NMAX){
bit[v] += val;
v += lsb(v);
}
}
int get(int pos){
int sum = 0;
while(pos){
sum += bit[pos];
pos -= lsb(pos);
}
return sum;
}
int sum(int l, int r){
return get(r) - get(l - 1);
}
vector <int> t(4 * NMAX);
void update(int v, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r){
t[v] = max(val, t[v]);
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int get(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return 0;
if(l >= st && r <= fin) return t[v];
int m = (l + r) / 2;
return max(get(2 * v, l, m, st, fin),
get(2 * v + 1, m + 1, r, st, fin));
}
map <int,int> mp;
int main(){
cin >> n;
int k; cin >> k;
int a[n + 1], b[n + 1];
int cur[n + 1];
vector <int> vec;
for(int i= 1; i<= n; i++){
cin >> a[i] >> b[i];
vec.pb(a[i]);
vec.pb(b[i]);
if(a[i] <= b[i]) cur[i] = 1;
else cur[i] = 0;
}
int t[k + 1];
for(int i = 1; i <= k; i++)
cin >> t[i];
for(int i = 1; i <= k; i++)
vec.pb(t[i]);
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
int x = vec[i];
mp[x] = i + 1;
}
for(int i = k; i >= 1; i--){
int v = t[i]; v = mp[v];
update(1, 1, 2 * n + k, v, i);
}
ll ans = 0;
vector <vector <int> > qv(2 * n + k + 1);
for(int i = 1; i <= n; i++){
int v = min(a[i], b[i]);
int u = max(a[i], b[i]);
int x = mp[v], y = mp[u]; y--;
int val = get(1, 1, 2 * n + k, x, y);
//cout << val << "\n";
qv[val].pb(i);
}
for(int i = k; i >= 1; i--){
int x= t[i]; x = mp[x];
add(x, 1);
for(int to : qv[i]){
int r = max(b[to], a[to]); r= mp[r];
int v = sum(r, NMAX - 1);
//cout << v << ' ' ;
if(v % 2 == 0) ans += (ll)max(b[to], a[to]);
else ans += (ll)min(b[to], a[to]);
}
//cout << "\n";
}
for(int to : qv[0]){
int r = max(b[to], a[to]); r = mp[r];
int v = sum(r, NMAX - 1);
v += cur[to];
if(v & 1) ans += (ll)min(b[to], a[to]);
else ans += (ll)max(b[to], a[to]);
}
cout << ans;
return 0;
}
Compilation message (stderr)
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |