Submission #1307700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307700		HoriaHaivas	Discharging (NOI20_discharging)	C++20	0 / 100	78 ms	15868 KiB

Discharging

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

int dp[1000005];
int v[1000005];
const int inf=1e9;
const int lim=1e9;

struct Line
{
    int a;
    int b;
    int eval(int x)
    {
        return a*x+b;
    }
};

struct Node
{
    int lson;
    int rson;
    Line lin;
};

Node emptyNode= {0,0,{inf,inf}};

class Lichao
{
public:

    int sz;
    Node aint[1000005];

    void init()
    {
        sz=0;
        aint[0]=emptyNode;
    }

    void insert_line(Line lin)
    {
        insert_line(-lim,lim,0,lin);
    }

    void insert_line(int l, int r, int val, Line lin)
    {
        int mid;
        bool tl,tm,tr;
        mid=(l+r)/2;
        tm=(lin.eval(mid)<aint[val].lin.eval(mid));
        if (tm)
            swap(aint[val].lin,lin);
        tl=(lin.eval(l)<aint[val].lin.eval(l));
        tm=(lin.eval(mid)<aint[val].lin.eval(mid));
        tr=(lin.eval(r)<aint[val].lin.eval(r));
        if (tl)
        {
            if (aint[val].lson!=0)
                insert_line(l,mid,aint[val].lson,lin);
            else
            {
                sz++;
                aint[val].lson=sz;
                aint[sz]=emptyNode;
                aint[sz].lin=lin;
            }
        }
        else if (tr)
        {
            if (aint[val].rson!=0)
                insert_line(mid+1,r,aint[val].rson,lin);
            else
            {
                sz++;
                aint[val].rson=sz;
                aint[sz]=emptyNode;
                aint[sz].lin=lin;
            }
        }
    }

    int query(int l, int r, int val, int x)
    {
        int ans,mid;
        ans=inf;
        mid=(l+r)/2;
        if (x<=mid)
        {
            ans=min(ans,aint[val].lin.eval(x));
            if (aint[val].lson!=0)
                ans=min(ans,query(l,mid,aint[val].lson,x));
        }
        else
        {
            ans=min(ans,aint[val].lin.eval(x));
            if (aint[val].rson!=0)
                ans=min(ans,query(mid+1,r,aint[val].rson,x));
        }
        return ans;
    }
} nsuh;

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,mx;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> v[i];
    }
    nsuh.init();
    nsuh.insert_line({n,0});
    mx=-1;
    for (i=1;i<=n;i++)
    {
         mx=max(mx,v[i]);
         dp[i]=nsuh.query(-lim,lim,0,mx);
         nsuh.insert_line({n-i,dp[i]});
    }
    cout << dp[n];
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28