Submission #933946

#	Time	Username	Problem	Language	Result	Execution time	Memory
933946		velislavgarkov	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	690 ms	84120 KiB

constellation3

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
struct Star {
    long long c;
    int x, y;
};
const int MAXN=2e5+10;
int n, m;
unordered_map <long long, int> um;
Star s[MAXN];
int a[MAXN], sp[MAXN][20], stepen[MAXN];
int in[MAXN], out[MAXN], in_tree[MAXN], cnt_in;
long long dp[MAXN], tree[4*MAXN];
vector <int> v[MAXN], zv[MAXN];
int cnt_tree;
void sparce_table() {
    for (int i=0;i<=n+1;i++) sp[i][0]=i;
    for (int i=1;(1<<i)<=n+2;i++) {
        for (int j=0;j+(1<<i)-1<=n+1;j++) {
            int i1=sp[j][i-1];
            int i2=sp[j + (1 << (i-1))][i-1];
            if (a[i1]>=a[i2]) sp[j][i]=i1;
            else sp[j][i]=i2;
        }
    }
    int cur_st=0;
    for (int i=1;i<=n+2;i++) {
        if ((1 << (cur_st+1))<i) cur_st++;
        stepen[i]=cur_st;
    }
}
int find_max(int l, int r) {
    if (l>r) return -1;
    int st=stepen[r-l+1];
    int i1, i2;
    i1=sp[l][st];
    i2=sp[r - (1 << st)+1][st];
    if (a[i1]>=a[i2]) return i1;
    return i2;
}
long long encode(long long l, long long r) {
    return l*((long long)n+2ll)+r;
}
void find_tree(int idx, int l, int r) {
    if (l+1>=r) return;
    um[encode(l,r)]=idx;
    cnt_in++;
    in[idx]=cnt_in;
    int cur_ind=find_max(l+1,r-1);
    int last=l, kopie=cur_ind;
    while (cur_ind!=-1 && a[cur_ind]==a[kopie]) {
        in_tree[cur_ind]=idx;
        if (last+1<cur_ind) {
            cnt_tree++;
            v[idx].push_back(cnt_tree);
            find_tree(cnt_tree,last,cur_ind);
        }
        last=cur_ind;
        cur_ind=find_max(cur_ind+1,r-1);
    }
    if (last+1<r) {
        cnt_tree++;
        v[idx].push_back(cnt_tree);
        find_tree(cnt_tree,last,r);
    }
    out[idx]=cnt_in;
}
void update(int node, int l, int r, int ql, int qr, long long ch) {
    if (ql>r || qr<l) return;
    if (l>=ql && r<=qr) {
        tree[node]+=ch;
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr,ch);
    update(node*2+1,mid+1,r,ql,qr,ch);
}
long long query(int node, int l, int r, int qind) {
    if (l==r) return tree[node];
    int mid=(l+r)/2;
    if (qind<=mid) return query(node*2,l,mid,qind)+tree[node];
    return query(node*2+1,mid+1,r,qind)+tree[node];
}
long long find_dist(int col, int par) {
    int x=in_tree[col];
    return query(1,1,cnt_in,in[x])-query(1,1,cnt_in,in[par]);
}
void find_dp(int x) {
    long long sum_ch=0;
    for (auto i:v[x]) {
        find_dp(i);
        sum_ch+=dp[i];
    }
    dp[x]=sum_ch;
    for (auto i:zv[x]) {
        dp[x]=max(dp[x],s[i].c+sum_ch+find_dist(s[i].x,x));
    }
    update(1,1,cnt_in,in[x],out[x],sum_ch-dp[x]);
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    a[0]=a[n+1]=n+1;
    sparce_table();
    find_tree(0,0,n+1);
    long long sum_st=0;
    cin >> m;
    for (int i=0;i<m;i++) {
        cin >> s[i].x >> s[i].y >> s[i].c;
        sum_st+=s[i].c;
        int l, r, mid, grl, grr;
        l=0; r=s[i].x-1;
        while (l<=r) {
            mid=(l+r)/2;
            if (a[find_max(mid,s[i].x-1)]<s[i].y) r=mid-1;
            else l=mid+1;
        }
        grl=r;
        l=s[i].x+1; r=n+1;
        while (l<=r) {
            mid=(l+r)/2;
            if (a[find_max(s[i].x+1,mid)]<s[i].y) l=mid+1;
            else r=mid-1;
        }
        grr=l;
        zv[um[encode(grl,grr)]].push_back(i);
    }
    find_dp(0);
    cout << sum_st-dp[0] << endl;
    return 0;
}

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