#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
if(p==0) return 1 % MOD;
long long r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
long long inv(long long b) {
return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) {
long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() {
for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
struct query {
int a, b;
int mi, ma;
};
bool cmp(query x, query y) {
return x.ma < y.ma;
}
struct segtree {
struct node {
int mi, cntmi;
int ma, cntma;
};
vector<node> st;
int stok;
void bu(int l, int r, int idx) {
if(l == r) {
st[idx].mi = 0;
st[idx].ma = 0;
st[idx].cntmi = 1;
st[idx].cntma = 1;
return;
}
int mid = (l + r) >> 1;
bu(l, mid, 2*idx+1);
bu(mid+1, r, 2*idx+2);
st[idx].mi = 0, st[idx].ma = 0;
st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi;
st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma;
}
void u(int l, int r, int tar, int idx, int val) {
if(l == r) {
st[idx].mi = st[idx].ma = val;
return;
}
int mid = (l+r) >> 1;
if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
else u(mid+1, r, tar, 2*idx+2, val);
st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
if(st[2*idx+1].mi == st[2*idx+2].mi) st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi;
else st[idx].cntmi = (st[2*idx+1].mi < st[2*idx+2].mi ? st[2*idx+1].cntmi : st[2*idx+2].cntmi);
if(st[2*idx+1].ma == st[2*idx+2].ma) st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma;
else st[idx].cntma = (st[2*idx+1].ma > st[2*idx+2].ma ? st[2*idx+1].cntma : st[2*idx+2].cntma);
}
int qu1(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
if(st[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl +constr) >> 1;
if(st[2*idx+2].ma >= val) constl = mid + 1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
if(mid < l || r <constl) return qu1(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1, val);
else {
int res = qu1(l, r, mid+1, constr, 2*idx+2, val);
if(res != -1) return res;
return qu1(l, r, constl, mid, 2*idx+1, val);
}
}
pair<int, int> qu2(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return {st[idx].mi, st[idx].cntmi};
int mid = (constl +constr) >> 1;
if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r <mid+1) return qu2(l,r ,constl, mid, 2*idx+1);
else {
pair<int, int> lchild = qu2(l, r, constl, mid, 2*idx+1);
pair<int, int> rchild = qu2(l, r, mid+1, constr, 2*idx+2);
if(lchild != rchild) return min(lchild, rchild);
else return {lchild.first, lchild.second + rchild.second};
}
}
public:
void resize(int k) {
stok = k;
st.resize(4*k + 10);
}
void build() {
bu(1, stok, 0);
}
void point_update(int i, int v) {
u(1, stok, i, 0, v);
}
int last_atleast(int l, int r, int v) {
return qu1(l, r, 1, stok, 0, v);
}
pair<int, int> min_cnt(int l, int r) {
return qu2(l, r, 1, stok, 0);
}
};
void solve(int tc) {
segtree st;
int n, k;
cin >> n >> k;
st.resize(k);
st.build();
query q[n];
for(int i=0; i<n; i++) {
cin >> q[i].a >> q[i].b;
q[i].mi = min(q[i].a, q[i].b);
q[i].ma = max(q[i].a, q[i].b);
}
sort(q, q+n, cmp);
vector<pair<int, int> > v;
for(int i=1; i<=k; i++) {
int y;
cin >> y;
v.push_back({y, i});
}
sort(v.begin(), v.end());
int vptr = 0;
int res = 0;
for(int i=0; i<n; i++) {
// cout << "original: " << q[i].a << ", final: ";
int og = res;
while(vptr != v.size() && v[vptr].first < q[i].ma) {
st.point_update(v[vptr].second, v[vptr].first);
//cout << "st[" << v[vptr].second << "] := " << v[vptr].first << "\n";
vptr++;
}
int idx = st.last_atleast(1, k, q[i].mi);
if(idx == -1) { // A operations only
pair<int, int> ono = st.min_cnt(1, k);
if(ono.first == 0 && ono.second % 2 == 1) { // changed
res += q[i].b;
}
else {
res += q[i].a;
}
}
else if(q[i].a == q[i].b) { // doesn't matter
res += q[i].a;
}
else if(idx + 1 > k) { // last operation is S
res += q[i].ma;
}
else {
pair<int, int> ono = st.min_cnt(idx + 1, k);
if(ono.first == 0 && ono.second % 2 == 1) { // changed
res += q[i].mi;
}
else {
res += q[i].ma;
}
}
}
cout << res << '\n';
}
int32_t main(){
precomp();
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
/*
1 3
4 6
8
2
9
*/
Compilation message
fortune_telling2.cpp: In function 'void solve(long long int)':
fortune_telling2.cpp:156:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | while(vptr != v.size() && v[vptr].first < q[i].ma) {
| ~~~~~^~~~~~~~~~~
fortune_telling2.cpp:155:9: warning: unused variable 'og' [-Wunused-variable]
155 | int og = res;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
2144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
