제출 #927020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927020		winter0101	별자리 3 (JOI20_constellation3)	C++14	100 / 100	470 ms	56396 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
struct star{
int x,y;
long long val;
}a[maxn];
int b[maxn];
vector<int>cord[maxn];
struct line{
int l,r,id;
bool operator < (const line &p)const {
if (l==p.l)return r>p.r;
return l<p.l;
}
};
vector<int>g[maxn];
int n,m;
multiset<line>tmp;
void cartasian(int l,int r,int node){
while (!tmp.empty()){
auto u=*tmp.begin();
if (l<=u.l&&u.r<=r){
g[node].pb(u.id);
tmp.erase(tmp.begin());
cartasian(u.l,u.r,u.id);
}
else return;
}
}
int l[maxn],r[maxn];
long long f[maxn];
long long bit[maxn];
int in[maxn],out[maxn],tme=0;
void add(int pos,long long val){
for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
long long get(int pos){
long long sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
void update(int l,int r,long long val){
add(l,val);
add(r+1,-val);
}
int st[maxn*4];
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id]=max(st[id],val);
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
}
int get(int id,int l,int r,int u){
if (l>u||r<u)return 0;
int ans=st[id];
if (l==r)return ans;
int mid=(l+r)>>1;
ans=max({ans,get(id<<1,l,mid,u),get(id<<1|1,mid+1,r,u)});
return ans;
}
int rev[maxn];
void dfs(int u){
if (u)in[u]=++tme;
update(1,1,n,l[u],r[u],in[u]);
f[u]=a[u].val;
for (auto v:g[u]){
dfs(v);
}
long long ss=0;
for (auto v:g[u]){
ss+=f[v];
}
if (u){
update(in[u],in[u],ss);
for (auto v:g[u]){
update(in[v],out[v],ss-f[v]);
}
int pos=get(1,1,n,a[u].x);
f[u]+=get(pos);
}
f[u]=max(f[u],ss);
if (u)out[u]=tme;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n;
    for1(i,1,n)cin>>b[i];
    b[0]=b[n+1]=n;
    cin>>m;
    for1(i,1,m){
    cin>>a[i].x>>a[i].y>>a[i].val;
    cord[a[i].x].pb(i);
    }
    deque<int>t;
    t.pb(0);
    for1(i,1,n){
    while (!t.empty()&&b[t.back()]<=b[i])t.pop_back();
    t.pb(i);
    for(auto v:cord[i]){
    int l1=0,r1=sz(t)-1;
    l[v]=0;
    while (l1<=r1){
    int mid=(l1+r1)/2;
    if (b[t[mid]]>=a[v].y){
    l[v]=t[mid];
    l1=mid+1;
    }
    else r1=mid-1;
    }
    l[v]++;
    }
    }
    t.clear();
    t.pb(n+1);
    for2(i,n,1){
    while (!t.empty()&&b[t.back()]<=b[i])t.pop_back();
    t.pb(i);
    for(auto v:cord[i]){
    int l1=0,r1=sz(t)-1;
    r[v]=n+1;
    while (l1<=r1){
    int mid=(l1+r1)/2;
    if (b[t[mid]]>=a[v].y){
    r[v]=t[mid];
    l1=mid+1;
    }
    else r1=mid-1;
    }
    r[v]--;
    }
    }
    l[0]=1,r[0]=n;
    for1(i,1,m)tmp.insert({l[i],r[i],i});
    cartasian(1,n,0);
    dfs(0);
    long long sum=0;
    for1(i,1,m)sum+=a[i].val;
    cout<<sum-f[0];
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65