Submission #1134753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134753		Zbyszek99	Constellation 3 (JOI20_constellation3)	C++20	35 / 100	1596 ms	88984 KiB

constellation3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

template<typename T>
class SPARSE_TABLE
{
    T** table;
    function<T(T,T)> func;
    int n;
    int* log;
    int max_b = 0;
    public:
    SPARSE_TABLE(int MAXN, function<T(T,T)> func) : func(func)
    {
        log = new int[MAXN+1];
        log[0] = -1;
        for(int i = 1; i <= MAXN; i++)
        {
            log[i] = log[i/2]+1;
        }
        n = 0;
        max_b = -1;
    }
    void setup(int N, T* v)
    {
        for(int i = 0; i <= max_b; i++)
        {
            delete[] table[i];
        }
        delete[] table;
        n = N;
        int max_lg = log[n];
        max_b = max_lg;
        table = new T*[max_lg+1];
        for(int i = 0; i <= max_lg; i++)
        {
            table[i] = new T[n];
        }
        for(int i = 0; i < n; i++)
        {
            table[0][i] = v[i];
        }
        for(int bit = 1; bit <= max_lg; bit++)
        {
            for(int i = 0; i < n; i++)
            {
                if(i + (1 << bit)-1 < n)
                {
                    table[bit][i] = func(table[bit-1][i],table[bit-1][i + (1 << (bit-1))]);
                }
            }
        }
    }
    T query(int l, int r)
    {
        int bit = log[r-l+1];
        return func(table[bit][l],table[bit][r-(1 << bit)+1]);
    }
};

struct dp
{
    set<int> poz;
    unordered_map<int,ll> ans;
    ll dod = 0;
    ll down_ans = 0;
    ll sum = 0;
    void upd()
    {
        forall(it,poz) ans[it]+=dod;
        dod = 0;
    }
    void merge(dp& d, int level)
    {
        d.upd();
        sum += d.sum;
        vi del;
        forall(it,poz)
        {
            if(it <= level)
            {
                down_ans = min(down_ans,ans[it]+dod);
                del.pb(it);
            }
        }
        while(!del.empty())
        {
            poz.erase(poz.find(del.back()));
            del.pop_back();
        }
        forall(it,d.poz)
        {
            if(it <= level)
            {
                d.down_ans = min(d.down_ans,d.ans[it]+d.dod);
                del.pb(it);
            }
        }
        while(!del.empty())
        {
            d.poz.erase(d.poz.find(del.back()));
            del.pop_back();
        }
       // cout << down_ans << " " << d.down_ans << " down_ans\n";
        dod += d.down_ans;
        forall(it,d.poz)
        {
            if(poz.find(it) == poz.end())
            {
                ans[it] = INF_L;
                poz.insert(it);
            }
            ans[it] = min(ans[it],d.ans[it]-dod+down_ans);
            auto up = poz.upper_bound(it);
            while(up != poz.end() && ans[*up] >= ans[it]+down_ans)
            {
                poz.erase(up);
                up = poz.upper_bound(it);
            }
        }
        down_ans += d.down_ans;
    }
    void add_star(vector<pair<int,ll>> stars)
    {
        forall(it,stars)
        {
            sum += it.ss;
            down_ans += it.ss;
        } 
        forall(it,stars)
        {
            int y = it.ff;
            if(poz.find(y) == poz.end())
            {
                ans[y] = INF_L;
                poz.insert(y);
            }
            ans[y] = min(ans[y],sum-it.ss);
            auto up = poz.upper_bound(y);
            while(up != poz.end() && ans[*up] >= sum-it.ss)
            {
                poz.erase(up);
                up = poz.upper_bound(y);
            }
        }
    }
};

vector<pair<int,ll>> stars[200001];
int arr[200001];
int pom[200001];
int max_f(int a, int b) {return arr[a] > arr[b] ? a : b;};

SPARSE_TABLE<int> table(200001,max_f);
dp dps[200001];

int f(int l, int r)
{
    if(l > r) return -1;
    int m = table.query(l,r);
    int p1 = f(l,m-1);
    int p2 = f(m+1,r);
    if(p1 != -1)
    {
        if(siz(dps[p1].poz) > siz(dps[m].poz)) swap(dps[m],dps[p1]);
        dps[m].merge(dps[p1],arr[m]);
    }
    if(p2 != -1)
    {
        if(siz(dps[p2].poz) > siz(dps[m].poz)) swap(dps[m],dps[p2]);
        dps[m].merge(dps[p2],arr[m]);
    }
   // cout << m << " tree\n";
   // forall(it,dps[m].poz)
   // {
   //     cout << it << " " << dps[m].ans[it] << " dp\n";
   // }
   // cout << dps[m].sum << " " << dps[m].dod << " " << dps[m].down_ans << " dod\n\n";
    return m;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n;
    cin >> n;
    rep(i,n) cin >> arr[i+1];
    rep2(i,1,n) pom[i] = i;
    table.setup(n+1,pom);
    int m;
    cin >> m;
    rep(i,m)
    {
        int x,y,c;
        cin >> x >> y >> c;
        stars[x].pb({y,c});
    }
    rep2(i,1,n)
    {
        dps[i].add_star(stars[i]);
    }
    int poz = f(1,n);
    dps[poz].upd();
    ll ans = dps[poz].down_ans;
    forall(it,dps[poz].poz)
    {
        ans = min(ans,dps[poz].ans[it]);
    }
    cout << ans << "\n";
}

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