Submission #640360

#	Time	Username	Problem	Language	Result	Execution time	Memory
640360		sumit_kk10	Discharging (NOI20_discharging)	C++17	13 / 100	1000 ms	24756 KiB

Discharging

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, a[N], dp[N];

struct Line{
    int m, c;

    int val(int x){
        return m*x + c;
    }
};

vector<pair<vector<Line>, int> > hulls;

vector<Line> merge(vector<Line> a, vector<Line> b){
    // a and b is already sorted in increasing order of slopes
    vector<Line> ans;
    int i = 0, j = 0;
    while(i < a.size() and j < b.size()){
        if(a[i].m >= b[j].m){
            ans.pb(a[i]);
            ++i;
        }
        else{
            ans.pb(b[j]);
            ++j;
        }
    }
    while(i < a.size()){
        ans.pb(a[i]);
        ++i;
    }
    while(j < b.size()){
        ans.pb(b[j]);
        ++j;
    }
    return ans;
}

bool check(Line a, Line b, Line c) {
    // do a and c cover b?
    long long left = (b.c - a.c);
    left = left * (b.m - c.m);
    long long right = (c.c - b.c);
    right = right * (a.m - b.m);
    return left > right;
}

bool cmp(Line a, Line b){
    if(a.m == b.m)
        return a.c < b.c;
    return a.m > b.m;
}

vector<Line> CHT(vector<Line> cur){
    sort(cur.begin(), cur.end(), cmp);
    vector<Line> temp;
    temp.pb(cur[0]);
    for(int i = 1; i < cur.size(); ++i){
        if(cur[i].m == temp.back().m)
            continue;
        temp.pb(cur[i]);
    }
    cur = temp;
    vector<Line> hull;
    hull.pb(cur[0]); // first line will always be in the hull
    if(cur.size() == 1)
        return hull;
    hull.pb(cur[1]); // assuming this line is also in the hull
    for(int j = 2; j < cur.size(); ++j){
        while(hull.size() > 1){
            Line pre = hull.back(), par = hull[hull.size() - 2];
            if(check(par, pre, cur[j]))
                hull.pop_back();
            else
                break;
        }
        hull.pb(cur[j]);
    }
    return hull;
}

void addLine(Line a){
    vector<Line> cur;
    cur.pb(a);
    hulls.pb({cur, 1});
    // you should merge last two if both are same size
    while(hulls.size() > 1){
        vector<Line> cur = hulls[hulls.size() - 1].F, pre = hulls[hulls.size() - 2].F;
        if(hulls[hulls.size() - 1].S == hulls[hulls.size() - 2].S){
            // merge these two hulls into one
            vector<Line> ans;
            ans = CHT(merge(pre, cur));
            int x = hulls[hulls.size() - 1].S + hulls[hulls.size() - 2].S;
            hulls.pop_back();
            hulls.pop_back();
            hulls.push_back({ans, x});
        }
        else
            break;
    }
}

int get(int x){
    int res = LLONG_MAX;
    for(int j = 0; j < hulls.size(); ++j){
        int low = 0, high = (int) hulls[j].F.size() - 2, ans = (int) hulls[j].F.size() - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(hulls[j].F[mid].val(x) <= hulls[j].F[mid + 1].val(x)){
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        res = min(res, hulls[j].F[ans].val(x));
    }
    return res;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i){
        Line cur;
        cur.m = n - i + 1, cur.c = dp[i - 1];
        addLine(cur);
        dp[i] = get(a[i]);
    }
    cout << dp[n] << "\n";
}
 
int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'std::vector<Line> merge(std::vector<Line>, std::vector<Line>)':
Discharging.cpp:25:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while(i < a.size() and j < b.size()){
      |           ~~^~~~~~~~~~
Discharging.cpp:25:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while(i < a.size() and j < b.size()){
      |                            ~~^~~~~~~~~~
Discharging.cpp:35:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(i < a.size()){
      |           ~~^~~~~~~~~~
Discharging.cpp:39:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
Discharging.cpp: In function 'std::vector<Line> CHT(std::vector<Line>)':
Discharging.cpp:65:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 1; i < cur.size(); ++i){
      |                    ~~^~~~~~~~~~~~
Discharging.cpp:76:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int j = 2; j < cur.size(); ++j){
      |                    ~~^~~~~~~~~~~~
Discharging.cpp: In function 'long long int get(long long int)':
Discharging.cpp:112:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::vector<Line>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int j = 0; j < hulls.size(); ++j){
      |                    ~~^~~~~~~~~~~~~~

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