/// ITNOG
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;
template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 32008, SQ = 110, INF = 1e9, LGN = 20, mod = 998244353, P = 131113;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct fenwick {
int fen[N];
void upd (int ind, int val){
ind += 3;
for (; ind < N; ind += ind & (-ind)){
fen[ind] += val;
}
}
int gett (int ind){
ind += 3;
int ret = 0;
for (; ind; ind -= ind & (-ind)){
ret += fen[ind];
}
return ret;
}
};
int n, k, ans, node[(3 * N) << 2], g[3 * N];
pii p[N], t[N];
vector <int> prs;
unordered_map <int, int> m;
fenwick fen;
void upd (int ind ,int val, int lx = 0, int rx = 3 * N, int x = 1){
if (rx - lx == 1){
node[x] = max (node[x], val);
return;
}
int md = (lx + rx) >> 1;
if (ind < md){
upd (ind, val, lx, md, x << 1);
}
else {
upd (ind, val, md, rx, x << 1 | 1);
}
node[x] = max (node[x << 1], node[x << 1 | 1]);
return;
}
int gett (int l, int r, int lx = 1, int rx = 3 * N, int x = 1){
if (l <= lx && rx <= r){
return node[x];
}
if (l >= rx || lx >= r){
return 0;
}
int md = (lx + rx) >> 1;
return max (gett (l, r, lx, md, x << 1), gett (l, r, md, rx, x << 1 | 1));
}
int32_t main(){
fast_io;
cin >> n >> k;
for (int i = 0; i < n; ++ i){
cin >> p[i].F >> p[i].S;
prs.pb(p[i].F);
prs.pb(p[i].S);
}
sort (p, p + n, [&](pii p1, pii p2) {return max (p1.F, p1.S) > max (p2.F, p2.S);});
for (int i = 0; i < k; ++ i){
cin >> t[i].F;
prs.pb(t[i].F);
t[i].S = i + 1;
}
sort (t, t + k, [&](pii t1, pii t2) {return t1.F > t2.F;});
sort (all(prs));
prs.resize(unique(all(prs)) - prs.begin());
for (int i = 0; i < prs.size(); ++ i){
m[prs[i]] = i + 1;
g[i+1] = prs[i];
}
for (int i = 0; i < n; ++ i){
p[i].F = m[p[i].F];
p[i].S = m[p[i].S];
}
for (int i = 0; i < k; ++ i){
t[i].F = m[t[i].F];
}
for (int i = 0; i < k; ++ i){
upd (t[i].F, t[i].S);
}
int pt = 0;
for (int i = 0; i < n; ++ i){
while (pt < k && t[pt].F >= max (p[i].F, p[i].S)){
fen.upd(t[pt].S, 1);
++ pt;
}
int lst = 0;
if (p[i].F != p[i].S){
lst = gett (min (p[i].F, p[i].S), max (p[i].F, p[i].S));
}
if (lst == 0){
ans += (fen.gett (N - 4) & 1 ? g[p[i].S] : g[p[i].F]);
}
else {
if (p[i].F > p[i].S){
swap (p[i].F, p[i].S);
}
ans += ((fen.gett (N - 4) - fen.gett (lst)) & 1 ? g[p[i].F] : g[p[i].S]);
}
}
cout << ans << '\n';
return 0;
}
// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:114:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i = 0; i < prs.size(); ++ i){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
