#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<19);
int n, q;
vector <pii> v, vec[N];
vector <int> que, saz;
int desaz[2*N], sol[N], Tmax[2*OFF], T[2*OFF], br[N];
#define DEBUG 0
int sazmi(int x) {
int ret=lower_bound(saz.begin(), saz.end(), x)-saz.begin();
desaz[ret]=x;
return ret;
}
int query_max(int a, int b, int pos=1, int lo=0, int hi=OFF) {
if (lo>=a && hi<=b) return Tmax[pos];
if (lo>=b || hi<=a) return -1;
int mid=(lo+hi)/2;
return max(query_max(a, b, pos*2, lo, mid), query_max(a, b, pos*2+1, mid, hi));
}
int query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
if (lo>=a && hi<=b) return T[pos];
if (lo>=b || hi<=a) return 0;
int mid=(lo+hi)/2;
return query(a, b, pos*2, lo, mid)+query(a, b, pos*2+1, mid, hi);
}
void update(int pos, int x) {
pos+=OFF; T[pos]+=x;
pos/=2;
while (pos) {
T[pos]=T[pos*2]+T[pos*2+1];
pos/=2;
}
}
void build() {
for (int i=OFF-1; i>0; --i) Tmax[i]=max(Tmax[i*2], Tmax[i*2+1]);
}
void solve() {
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
memset(Tmax, -1, sizeof Tmax);
for (int i=0; i<q; ++i) {
que[i]=sazmi(que[i]);
Tmax[OFF+que[i]]=i;
}
build();
for (int i=0; i<n; ++i) {
v[i].X=sazmi(v[i].X); v[i].Y=sazmi(v[i].Y);
int mn=min(v[i].X, v[i].Y), mx=max(v[i].X, v[i].Y);
int pos=query_max(mn, mx);
br[i]=pos;
vec[pos+1].pb(mp(mx, i));
}
for (int i=q-1; i>0; --i) {
update(que[i], 1);
for (pii pp:vec[i]) sol[pp.Y]=query(pp.X, OFF);
}
#if DEBUG
for (int i=0; i<n; ++i) {
printf("%d %d\n", v[i].X, v[i].Y);
}
for (int x:que) printf("%d\n", x);
#endif // DEBUG
ll res=0;
for (int i=0; i<n; ++i) {
int curr;
if (br[i]==-1) curr=sol[i]%2 ? v[i].Y : v[i].X;
else {
if (v[i].X>v[i].Y) swap(v[i].X, v[i].Y);
curr=sol[i]%2 ? v[i].X : v[i].Y;
}
res+=desaz[curr];
#if DEBUG
printf("i: %d, pos: %d, sol: %d, curr: %d\n", i, br[i], sol[i], curr);
#endif
}
printf("%lld\n", res);
}
void load() {
scanf("%d %d", &n, &q);
for (int i=0; i<n; ++i) {
int a, b;
scanf("%d %d", &a, &b);
saz.pb(a); saz.pb(b);
v.pb(mp(a, b));
}
for (int i=0; i<q; ++i) {
int x;
scanf("%d", &x);
que.pb(x); saz.pb(x);
}
}
int main() {
load();
solve();
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void load()':
fortune_telling2.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
113 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9196 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9196 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9196 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
