#include <bits/stdc++.h>
using namespace std;
/*
foco no cara da esquerda ativado ou nn
query so na esquerda: desligo
na direita: mudo
query so na esquerda:
desliga esquerda
nn mexe em direita
depois de query na esquerda ele sempre vai ficar com direita ativa
olhar ultima query na esquerda
depois só importam queries na direita
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN=2e5+10, MAXTT = 2*MAXN, BIG = 1e9+10;
pii c[MAXN];
bool ac[MAXN];
int seg[4*MAXN], lg[MAXN];
void build(int id, int il, int ir, vector<pii> &op){
if (il==ir){
seg[id]=op[il-1].second;
return;
}
int m = (il+ir)/2;
build(2*id, il, m, op);
build(2*id+1, m+1, ir, op);
seg[id] = max(seg[2*id], seg[2*id+1]);
}
int qry(int id, int il, int ir, int l, int r){
if (il>r || ir<l) return -BIG;
if (il>=l && ir<=r) return seg[id];
int m = (il+ir)/2;
return max(qry(2*id, il, m, l, r), qry(2*id+1, m+1, ir, l, r));
}
pii lst[MAXN];
int p[MAXN];
int bit[MAXN];
int bqry(int p){
int ss = 0;
while (p>0){
ss += bit[p];
p -= p&-p;
}
return ss;
}
void bup(int p, int v, int sz){
while (p<=sz){
bit[p]+=v;
p += p&-p;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
int a, b;
vector<pair<int, pii>> comp;
for (int i=0;i<n;i++){
cin >> a >> b;
if (a<b) ac[i]=1;
else swap(a,b);
c[i] = {a,b}, lg[i]=b;
comp.push_back({b,{i, 0}});
}
vector<pii> op(k+1);
for (int i=0;i<k;i++){
cin >> p[i+1];
op[i] = {p[i+1], i+1};
comp.push_back({p[i+1], {i+1, 1}});
}
sort(op.begin(), op.end());
build(1, 1, k, op);
for (int i=0;i<n;i++){
int l, r;
pii srch = {c[i].second, -1};
r = lower_bound(op.begin(), op.end(), srch) - op.begin(), srch = {c[i].first, -1}, l = lower_bound(op.begin(), op.end(), srch) - op.begin() + 1;
if (l<=r) lst[i].first = qry(1, 1, k, l, r);
lst[i].second = i;
}
sort(lst,lst+n); // ordena por ultimo que importa
// comprime qries com caras da direita
sort(comp.begin(), comp.end());
int cr = 1;
for (int i=0;i<comp.size();i++){
if (i>0 && comp[i].first != comp[i-1].first) cr++;
if (comp[i].second.second) p[comp[i].second.first] = cr;
else c[comp[i].second.first].second = cr;
}
int j = n-1; // primeiro q nn pega
while (j>=0 && lst[j].first==k) j--;
for (int i=k;i>0&&j>=0;i--){
// atualiza
bup(cr-p[i]+1, 1, cr);
if (lst[j].first == i){
int am = bqry(cr-c[lst[j].second].second+1);
// cerr << lst[j].second << ": " << am << " so " << ac[lst[j].second] << '\n';
ac[lst[j].second] = (am%2 == 1);
j--;
}
}
while (j>=0){ // quem só pega no direito
int am = bqry(cr-c[lst[j].second].second+1);
ac[lst[j].second] ^= (am%2 == 1);
// cerr << lst[j].second << ": " << am << " so " << ac[lst[j].second] << '\n';
j--;
}
long long ss = 0;
for (int i=0;i<n;i++){
if (ac[i]) ss += c[i].first;
else ss += lg[i];
}
cout << ss << '\n';
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i=0;i<comp.size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
