#include <bits/stdc++.h>
using namespace std ;
// #define test
#ifndef test
#include "nile.h"
#endif
////////////////////////////////////////////////////////////////////////
int gp[100003] ;
int gpmn[100003] ;
int gpmx[100003] ;
int gpsz[100003] ;
int tt=0 ;
struct SEGT {
int seg[400003] ;
void build(){
for (int i = 0 ; i < 400003 ; i ++) seg[i]=INT_MAX/2 ;
}
void upd(int id,int l,int r,int x,int v){
if (l==r&&l==x) seg[id]=min(seg[id],v) ;
else if (l>x||r<x) ;
else {
int md=(l+r)/2 ;
upd(id*2,l,md,x,v) ;
upd(id*2+1,md+1,r,x,v) ;
seg[id]=min(seg[id*2],seg[id*2+1]) ;
}
}
int qq(int id,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return seg[id] ;
else if (l>qr||r<ql) return INT_MAX/2 ;
else {
int md=(l+r)/2 ;
return min(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
}
}
} sgt[2],sgtst[2] ;
int N ;
int fnd(int x){
int a=gpmn[x],b=gpmx[x] ;
if ((b-a+1)%2==0) return 0 ;
else {
int mn=INT_MAX ;
mn=min(mn,sgt[a%2].qq(1,1,N,a+1,b+1)) ;
mn=min(mn,sgtst[(a+1)%2].qq(1,1,N,a+1,b+1)) ;
return mn ;
}
}
int dsu(int x){
if (x==gp[x]) return x ;
gp[x]=dsu(gp[x]) ;
return gp[x] ;
}
void merge(int a,int b){
a=dsu(a),b=dsu(b) ;
tt-=fnd(a) ;
tt-=fnd(b) ;
gp[b]=a ;
gpsz[a]+=gpsz[b] ;
gpmn[a]=min(gpmn[a],gpmn[b]) ;
gpmx[a]=max(gpmx[a],gpmx[b]) ;
tt+=fnd(a) ;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int Q = (int)E.size();
N=W.size() ;
sgt[0].build() ;
sgt[1].build() ;
sgtst[0].build() ;
sgtst[1].build() ;
std::vector<long long> R(Q, 0);
int i,j ;
vector <pair<int,int>> qs ;
for (i = 0 ; i < Q ; i ++){
qs.push_back({E[i],i}) ;
}
sort(qs.begin(),qs.end()) ;
vector <pair<int,int>> v ;
for (i = 0 ; i < N ; i ++){
tt+=A[i] ;
v.push_back({W[i],A[i]-B[i]}) ;
}
sort(v.begin(),v.end()) ;
for (i = 0 ; i < N ; i ++){
gp[i]=i ;
gpmn[i]=i ;
gpmx[i]=i ;
gpsz[i]=1 ;
sgt[i%2].upd(1,1,N,i+1,v[i].second) ;
}
vector<pair<int,int>> vv ;
vector<pair<int,int>> vv2 ;
for (i = 0 ; i < N-1 ; i ++){
vv.push_back({v[i+1].first-v[i].first,i}) ;
}
for (i = 0 ; i < N-2 ; i ++){
vv2.push_back({v[i+2].first-v[i].first,i+1}) ;
}
sort(vv.begin(),vv.end()) ;
sort(vv2.begin(),vv2.end()) ;
int nw=0 ;
int nw2=0 ;
for (i = 0 ; i < Q ; i ++){
int x=qs[i].first ;
while (nw2<vv2.size()&&vv2[nw2].first<=x){
sgtst[vv2[nw2].second%2].upd(1,1,N,vv2[nw2].second+1,v[vv2[nw2].second].second) ;
nw2++ ;
}
while (nw<vv.size()&&vv[nw].first<=x){
merge(vv[nw].second,vv[nw].second+1) ;
nw++ ;
}
R[qs[i].second]=tt ;
}
return R;
}
////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
// #include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> W(N), A(N), B(N);
for (int i = 0; i < N; i++)
assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> E(Q);
for (int j = 0; j < Q; j++)
assert(1 == scanf("%d", &E[j]));
fclose(stdin);
std::vector<long long> R = calculate_costs(W, A, B, E);
int S = (int)R.size();
for (int j = 0; j < S; j++)
printf("%lld\n", R[j]);
fclose(stdout);
return 0;
}
//grader}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |