#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node1{
ll s, e, m, val, lazy;
node1 *l, *r;
node1(ll S, ll E){
s = S, e = E, m = (s+e)/2;
val = 0;
lazy = 0;
if(s != e){
l = new node1(s,m);
r = new node1(m + 1,e);
}
}
void propogate(){
if(lazy==0) return;
val = max(val,lazy);
if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
l->lazy = max(l -> lazy,lazy);
r->lazy = max(r -> lazy,lazy);
}
lazy = 0;
}
void update(int S, int E, ll V){
if(s == S && e == E) lazy = max(lazy,V);
else{
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
val = max(l->val,r->val);
}
}
ll query(int S, int E){
propogate(); //remember to propogate
if(s == S && e == E) return val;
else if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return max(l->query(S, m),r->query(m+1, E));
}
} *root1;
struct node{
ll s, e, m, val, lazy;
node *l, *r;
node(ll S, ll E){
s = S, e = E, m = (s+e)/2;
val = 0;
lazy = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void propogate(){
if(lazy==0) return;
val += lazy*(e-s+1);
if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
l->lazy += lazy;
r->lazy += lazy;
}
lazy = 0;
}
void update(int S, int E, ll V){
if(s == S && e == E) lazy += V;
else{
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
val = l->val + r->val;
}
}
ll query(int S, int E){
propogate(); //remember to propogate
if(s == S && e == E) return val;
else if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return l->query(S, m) + r->query(m+1, E);
}
} *root2;
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,K;
cin>>N>>K;
root1 = new node1(0,MAXN);
root2 = new node(0,MAXN);
ll A[N], B[N], a[N], b[N];
vector<ll> d;
for(ll i = 0;i < N;i++){
cin>>A[i]>>B[i];
a[i] = A[i];
b[i] = B[i];
d.push_back(A[i]);
d.push_back(B[i]);
}
ll T[K];
for(ll i = 0;i < K;i++){
cin>>T[i];
d.push_back(T[i]);
}
sort(d.begin(),d.end());
d.resize(unique(d.begin(),d.end()) - d.begin());
for(ll i = 0;i < N;i++){
A[i] = lower_bound(d.begin(),d.end(),A[i]) - d.begin();
B[i] = lower_bound(d.begin(),d.end(),B[i]) - d.begin();
}
for(ll i = 0;i < K;i++){
T[i] = lower_bound(d.begin(),d.end(),T[i]) - d.begin();
}
vector<ll> v[MAXN]; //stores the i
for(ll i = 0;i < N;i++){
v[A[i]].push_back(i);
v[B[i]].push_back(i);
}
for(ll k = 0;k < K;k++){
root1 -> update(T[k],T[k],k + 1); //k is 1-indexed
}
vector<ll> start11[MAXN];
ll side[N];
memset(side,0,sizeof(side));
for(ll i = 0;i < N;i++){
if(A[i] == B[i]){
start11[0].push_back(i);
side[i] = 0;
continue;
}
ll num = root1 -> query(min(A[i],B[i]),max(A[i],B[i]) - 1);
num--;
if(num >= 0){
start11[num + 1].push_back(i);
if(A[i] < B[i]) side[i] = 1;
else side[i] = 0;
}else{
start11[0].push_back(i);
side[i] = 0;
}
}
deque<pair<ll,ll> > dq;
for(ll i = 0;i < K;i++){
dq.push_back({T[i],i});
}
sort(dq.begin(),dq.end(),greater<pair<ll,ll> >());
ll numof11[N];
memset(numof11,0,sizeof(numof11));
for(ll i = K - 1;i >= 0;i--){
while(!dq.empty() && dq.front().second >= i){
root2 -> update(dq.front().first,dq.front().first,1);
dq.pop_front();
}
for(auto u : start11[i]){
numof11[u] = root2 -> query(max(A[u],B[u]),MAXN);
}
}
ll sum = 0;
for(ll i = 0;i < N;i++){
if(side[i] == 0){
if(numof11[i] % 2 == 1) sum += b[i];
else sum += a[i];
}else if(side[i] == 1){
if(numof11[i] % 2 == 0) sum += a[i];
else sum += b[i];
}
}
cout<<sum<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
