#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
const ll INF = 1e16;
#define f first
#define s second
struct st{
ll ini,fin;
st *l,*r;
vector <ll> v;
st (ll INI, ll FIN) {
ini = INI;
fin = FIN;
l = nullptr;
r = nullptr;
}
};
pair <ll,ll> num[MAXN];
ll op[MAXN], act[MAXN], ans;
void setup(st *nodo) {
if (nodo->ini==nodo->fin) {
nodo->v.push_back(op[nodo->ini]);
return;
}
nodo->l = new st(nodo->ini,(nodo->ini+nodo->fin)/2);
nodo->r = new st((nodo->ini+nodo->fin)/2+1,nodo->fin);
setup(nodo->l);
setup(nodo->r);
int i=0,j=0;
while (i<nodo->l->v.size() && j<nodo->r->v.size()) {
if (nodo->l->v[i] > nodo->r->v[j]) {
nodo->v.push_back(nodo->r->v[j]);
j++;
}
else {
nodo->v.push_back(nodo->l->v[i]);
i++;
}
}
while (i<nodo->l->v.size()) {
nodo->v.push_back(nodo->l->v[i]);
i++;
}
while (j<nodo->r->v.size()) {
nodo->v.push_back(nodo->r->v[j]);
j++;
}
return;
}
ll bin(st *nodo, ll ini, ll fin, ll x) {
if (ini==fin) return ini;
if (nodo->v[(ini+fin)/2] > x) return bin(nodo,ini,(ini+fin)/2,x);
else return bin(nodo,(ini+fin)/2+1,fin,x);
}
ll query(st *nodo, ll L, ll R, ll x) {
if (L>nodo->fin || nodo->ini>R) return 0;
if (L<=nodo->ini && nodo->fin<=R) return bin(nodo,0,nodo->v.size(),x);
return query(nodo->l,L,R,x) + query(nodo->r,L,R,x);
}
ll cami(st *nodo, ll x1, ll x2) {
if (nodo->ini==nodo->fin) return nodo->ini;
if (bin(nodo->r,0,nodo->r->v.size(),x2) - bin(nodo->r,0,nodo->r->v.size(),x1-1) > 0) return cami(nodo->r,x1,x2);
else return cami(nodo->l,x1,x2);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,k,in;
cin>>n>>k;
for (int i=0;i<n;i++) {
cin>>num[i].f>>num[i].s;
act[i] = num[i].f;
if (num[i].f>num[i].s) swap(num[i].f,num[i].s);
}
for (int i=0;i<k;i++) cin>>op[i];
st *nodo = new st(0,k-1);
setup(nodo);
for (int i=0;i<n;i++) {
if (bin(nodo,0,nodo->v.size(),num[i].s-1) - bin(nodo,0,nodo->v.size(),num[i].f-1) > 0) {
act[i] = num[i].s;
in = cami(nodo,num[i].f,num[i].s-1) + 1;
}
else in = 0;
if ((k-in-query(nodo,in,k-1,num[i].f-1))%2==1) {
if (act[i]==num[i].f) act[i] = num[i].s;
else act[i] = num[i].f;
}
ans += act[i];
}
cout<<ans;
return 0;
}
Compilation message
fortune_telling2.cpp:1:10: fatal error: factories.h: No such file or directory
1 | #include "factories.h"
| ^~~~~~~~~~~~~
compilation terminated.
