Submission #219051

#	Time	Username	Problem	Language	Result	Execution time	Memory
219051		Akashi	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	510 ms	45328 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

struct stea{
    int x, y, c;
};

int n, m;
stea a[200005];
bool active[200005];
set <pair <int, int> > ev[200005];

struct dsu{
    int par[200005], sz[200005], st[200005], dr[200005];
    long long val[200005];

    void init(int n){
        for(int i = 1; i <= n ; ++i){
            par[i] = i; sz[i] = 1; val[i] = 0;
            st[i] = dr[i] = i;
        }
    }

    int find(int x){
        if(x != par[x]) return (par[x] = find(par[x]));
        return x;
    }

    void merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return ;

        if(sz[x] < sz[y]) swap(x, y);
        par[y] = x;

        sz[x] += sz[y];
        val[x] += val[y];

        st[x] = min(st[x], st[y]);
        dr[x] = max(dr[x], dr[y]);
    }

    void update(long long cand, int x){
        x = find(x);
        val[x] = max(val[x], cand);
    }

    bool inside(int point, int wh){
        wh = find(wh);
        if(st[wh] <= point && point <= dr[wh]) return true;
        return false;
    }
};

dsu comp;

struct segTree{
    long long lazy[800005];

    void propag(int nod){
        for(int i = nod * 2; i <= nod * 2 + 1 ; ++i) lazy[i] += lazy[nod];
        lazy[nod] = 0;
    }

    void update(int x, int y, long long val, int st = 1, int dr = n, int nod = 1){
        if(x <= st && dr <= y){
            lazy[nod] += val;
            return ;
        }
        if(lazy[nod]) propag(nod);

        int mij = (st + dr) / 2;
        if(x <= mij) update(x, y, val, st, mij, nod * 2);
        if(mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
    }

    long long query(int x, int st = 1, int dr = n, int nod = 1){
        if(st == dr) return lazy[nod];
        if(lazy[nod]) propag(nod);

        int mij = (st + dr) / 2;
        if(x <= mij) return query(x, st, mij, nod * 2);
        return query(x, mij + 1, dr, nod * 2 + 1);
    }

};

segTree A;

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);
    int x;
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x);
        ev[x + 1].insert({0, i});
    }

    scanf("%d", &m);
    long long Sum = 0;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
        ev[a[i].y].insert({1, i});
        Sum = Sum + a[i].c;
    }

    comp.init(n);

    for(int i = 1; i <= n ; ++i){
        int Last = -1;
        long long Max = 0;
        for(auto it : ev[i]){
            int tip = it.first, pos = it.second;
            if(tip == 0){
                active[pos] = 1;
                if(active[pos - 1]){
                    A.update(pos, pos, -comp.val[comp.find(pos - 1)]);
                    comp.merge(pos, pos - 1);
                }
                if(active[pos + 1]){
                    A.update(comp.st[comp.find(pos)], comp.dr[comp.find(pos)], -comp.val[comp.find(pos + 1)]);
                    A.update(comp.st[comp.find(pos + 1)], comp.dr[comp.find(pos + 1)], -comp.val[comp.find(pos)]);
                    comp.merge(pos, pos + 1);
                }
            }
            else{
                if(Last == -1) ;
                else if(!comp.inside(a[pos].x, Last)){
                    int x = comp.find(Last);
                    comp.update(Max, Last);

                    Max = 0;
                }

                Last = a[pos].x;
                Max = max(Max, a[pos].c - A.query(a[pos].x));
            }
        }

        if(Last != -1){
            int x = comp.find(Last);
            comp.update(Max, Last);
        }
    }

    for(int i = 1; i <= n ; ++i)
        if(comp.dr[comp.find(i)] == i) Sum = Sum - comp.val[comp.find(i)];

    printf("%lld", Sum);
    return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:131:25: warning: unused variable 'x' [-Wunused-variable]
                     int x = comp.find(Last);
                         ^
constellation3.cpp:143:17: warning: unused variable 'x' [-Wunused-variable]
             int x = comp.find(Last);
                 ^
constellation3.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
constellation3.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
constellation3.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
constellation3.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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