Submission #230063

#	Time	Username	Problem	Language	Result	Execution time	Memory
230063		anonymous	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	491 ms	45036 KiB

constellation3

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
#define MAXN 200005
#define LL long long
#define fi first
#define se second
using namespace std;
int N, M, A[MAXN], X[MAXN], Y[MAXN], C[MAXN];
int Start[MAXN], End[MAXN], Par[MAXN], Order[MAXN];
LL dp[MAXN], Ans;
vector <pair<int,int> > B, Star[MAXN]; //buildings
vector <int> adj[MAXN];
set<pair<int,int> > Active, S;

class fenwick {
    LL BIT[MAXN];
    void add(int p, LL x) {
        for (; p<=N+3; p+=p&(-p)) {BIT[p]+=x;}
    }
    LL PrefSum(int p) {
        LL res = 0;
        for (; p>0; p-=p&(-p)) {res+=BIT[p];}
        return(res);
    }
public:
    void upd(int l, int r, LL x) {
        add(l, x);
        add(r+1, -x);
    }
    LL ask(int p) {return(PrefSum(p));} //point query
} FT;

LL slv(int u) { //cost to resolve the tree
    dp[u] = C[u];
    for (int v: adj[u]) {
        dp[u] += slv(v);
    }
    for (int v: adj[u]) {
        FT.upd(Start[v], End[v], C[v]);
        FT.upd(Start[u], Start[v]-1, dp[v]);
        FT.upd(End[v]+1, End[u], dp[v]);
    }
    dp[u] = min(dp[u], FT.ask(X[u]));
    return(dp[u]);
}

int main() {
    //freopen("star3in.txt","r",stdin);
    scanf("%d",&N);
    for (int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
    }
    A[N+1] = 1 << 30;
    B.push_back({2e9,  0});
    scanf("%d",&M);
    for (int i=1; i<=M; i++) {
        scanf("%d %d %d",&X[i],&Y[i],&C[i]);
        Star[X[i]].push_back({Y[i],i});
    }

    //find intervals
    for (int i=1; i<=N+1; i++) {
        while (B.size()&& B.back().fi <= A[i]) {B.pop_back();}
        B.push_back({A[i],i});
        for (auto s: Star[i]) {
            int lo = -1, hi = B.size();
            while (lo + 1 != hi) {
                int mid = (lo + hi) >> 1;
                if (B[mid].fi >= s.fi) {lo = mid;}
                else {hi = mid;}
            }
            Start[s.se] = B[lo].se + 1;
            Active.insert(s);
        }
        for (auto p = Active.begin(); p != Active.end(); ) {
            auto P = *p;
            if (P.fi > A[i]) {break;}
            End[P.se] = i-1;
            p = Active.erase(p);
        }
    }

    //build MIS on tree
    for (int i=1; i<=M; i++) {
        Order[i] = i;
    }
    sort(Order+1, Order+M+1, [](int a, int b) {return(End[a] - Start[a] < End[b] - Start[b]);});
    for (int i=1; i<=M; i++) {
        auto pt = S.lower_bound({Start[Order[i]],-1});
        while (pt != S.end() && (*pt).fi <= End[Order[i]]) {
            Par[(*pt).se] = Order[i];
            adj[Order[i]].push_back((*pt).se);
            pt = S.erase(pt);
        }
        S.insert({Start[Order[i]], Order[i]});
    }

    //dp
    for (int i=1; i<=M; i++) {
        if (!Par[i]) {Ans += slv(i);}
    }
    printf("%lld", Ans);
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
constellation3.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~
constellation3.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&M);
     ~~~~~^~~~~~~~~
constellation3.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&X[i],&Y[i],&C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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