Submission #230052

#	Time	Username	Problem	Language	Result	Execution time	Memory
230052		anonymous	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	11 ms	9984 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);}
    LL res2 = 0;
    dp[u] = min(dp[u], FT.ask(X[u]));
    if (Par[u]) {
        FT.upd(Start[u], End[u], C[u]);
        FT.upd(Start[Par[u]], Start[u]-1, dp[u]);
        FT.upd(End[u]+1, End[Par[u]], dp[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++) { //bugged
        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 'long long int slv(int)':
constellation3.cpp:39:8: warning: unused variable 'res2' [-Wunused-variable]
     LL res2 = 0;
        ^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
constellation3.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~
constellation3.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&M);
     ~~~~~^~~~~~~~~
constellation3.cpp:59: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: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65