Submission #736072

#	Time	Username	Problem	Language	Result	Execution time	Memory
736072		Ronin13	Discharging (NOI20_discharging)	C++14	100 / 100	282 ms	92916 KiB

Discharging

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 10000001;


struct line{
    ll k, b;
    line(ll k, ll b) : k(k), b(b){

    }
    line(){
        k = 0, b = 1e18;
    }
    ll get(ll x){
        return k * x + b;
    }
};

vector <line> t;

vector <int> le(nmax), ri(nmax);

void add(int v, int l, int r, line nw){
    int m = (l + r) / 2;
    if(l > r){
        return;
    }
    bool left = t[v].get(l) < nw.get(l);
    bool mid = t[v].get(m) < nw.get(m);
    if(!mid) swap(t[v], nw);
    if(mid == left){
        if(ri[v] == 0){
            ri[v] = t.size();
            t.pb(nw);
            return;
        }
        add(ri[v], m + 1, r, nw);
    }
    else{
        if(le[v] == 0)
            le[v] = t.size(), t.pb(nw);
        else add(le[v], l, m, nw);
    }
}

ll get(int v, int l, int r, ll pos){
    if(l > r || v == 0) return 1e18;
    ll m = (l + r) / 2;
    if(pos > m)
        return min(t[v].get(pos), get(ri[v], m + 1, r, pos));
    return min(t[v].get(pos), get(le[v], l, m, pos));
}

line empt;

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    t.pb(empt);

    int n; cin >> n;
    t.pb({n, 0});
    vector <int> a(n + 1);
    vector <int> b;
    int mx = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(a[i] > mx){
            b.pb(i);
            mx = a[i];
        }
    }
    ll ans = 0;
    for(int i= 0; i < b.size(); i++){
        int x = b[i];
        ll val = get(1, 1, 1e9, a[x]);
        ans = val;
        if(i != b.size() - 1){
            int x = b[i + 1] - 1;
             add(1, 1, 1e9, {n - x, ans});
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int32_t main()':
Discharging.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i= 0; i < b.size(); i++){
      |                   ~~^~~~~~~~~~
Discharging.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if(i != b.size() - 1){
      |            ~~^~~~~~~~~~~~~~~

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