#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
//#pragma GCC optimize("fast-math")
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
#include<algorithm>
#include<bitset>
#include<map>
#include<iomanip>
#include<set>
#include<string.h>
#include<stack>
#include <list>
#include <numeric>
#include <random>
#include<unordered_map>
#define all(x) x.begin(), x.end()
#define ln (e-s+1)
#define lc (id<<1)
#define rc ((id<<1) | 1)
#define md ((e+s)>>1)
#define dm (((e+s)>>1)+1)
#define pb push_back
#define ll long long
#define endl '\n'
#define mk make_pair
#define F first
#define pll pair<ll, ll>
#define S second
#define pvv pair<vector<int> , vector<int> >
#define pii pair<int,int>
#define plll pair<ll, pair<int, int> >
#define ld long double
#define mat vector<vector<ll>>
//#define int long long
using namespace std;
const int N = (int)2e5 + 2, mod = (int) 1e9 + 7;
int n, k, a[N], b[N], sum[N * 3], qer[N], nsa[N], ansi[N], t[N], mn, mx;
vector<int> seg[N * 3];
vector<pii> vec, cev;
bool bl[N];
void build(int id = 1,int s = 1,int e = k){
if(ln == 1){
seg[id].pb(t[s]);
return;
}build(lc, s, md), build(rc, dm, e);
for(int x : seg[lc]) seg[id].pb(x);
for(int x : seg[rc]) seg[id].pb(x);
sort(seg[id].begin(), seg[id].end());
}
int get(int l2,int r2,int id = 1,int s = 1,int e = k){
if( l2 <= s && e <= r2){
int l = 0, r = seg[id].size() - 1, ans = -1;
while(l <= r){
int mid = (l+r) >> 1;
if(seg[id][mid] >= mn) ans = mid, r = mid - 1;
else l = mid + 1;
}
if(ans == -1) return mod;
return seg[id][ans];
}
int g1 = mod, g2 = mod;
if(!(l2 > md || r2 < s))g1 = get(l2, r2, lc, s, md);
if(!(l2 > e || r2 < dm))g2 = get(l2, r2, rc, dm, e);
return min(g1, g2);
}
void updsm(int p,int id = 1,int s = 1,int e = k){
if(ln == 1){
sum[id] ++;
return;
}
if(p <= md) updsm(p, lc, s, md);
else updsm(p, rc, dm, e);
sum[id] = sum[lc] + sum[rc];
}
int getsm(int l,int r,int id = 1,int s = 1,int e = k){
if(l > e || r < s) return 0;
if(l <= s && e <= r) return sum[id];
int g1 = 0, g2 = 0;
if(!(l > md || r < s))g1 = getsm(l, r, lc, s, md);
if(!(l > e || r < dm))g2 = getsm(l, r, rc, dm, e);
return g1 + g2;
}
int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++)
scanf("%d%d", &a[i],&b[i]), vec.pb({max(a[i], b[i]), i}),cev.pb({min(a[i], b[i]), i});
for(int i = 1; i <= k; i ++) scanf("%d", &t[i]), vec.pb({t[i], i + n}), cev.pb({t[i], i + n});
sort(cev.begin(), cev.end());
reverse(cev.begin(), cev.end());
build();
ll ret = 0;
set<pii> st;
for(auto [x, y] : cev){
if(y > n) st.insert({-x,-(y-n)});
else ansi[y] = -((*st.upper_bound({-max(a[y],b[y]),-mod})).S);
}
for(int i = 1; i <= n; i ++){
qer[i] = ansi[i];
if(get(1, ansi[i] - 1) < mx)bl[i] = 1;
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for(auto [x, y] : vec){
if(y > n) updsm(y-n);//,cout << endl;
else nsa[y] = getsm(qer[y] , k);//,cout << " few " << " , " << qer[y] << " " <<getsm(qer[y], k) << endl;
}
for(int i = 1; i <= n; i ++){
if(bl[i]){
if(nsa[i]%2) ret += min(a[i], b[i]);
else ret += max(a[i], b[i]);
}else{
if(nsa[i]%2) ret += b[i];
else ret += a[i];
}
}
cout << ret << endl;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d%d", &a[i],&b[i]), vec.pb({max(a[i], b[i]), i}),cev.pb({min(a[i], b[i]), i});
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:95:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | for(int i = 1; i <= k; i ++) scanf("%d", &t[i]), vec.pb({t[i], i + n}), cev.pb({t[i], i + n});
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
