Submission #1302755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302755		jjaewon	Discharging (NOI20_discharging)	C++20	11 / 100	175 ms	102164 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(x) x.begin(),x.end()
const int INF=1e9;
const ll LINF=1e18;

struct Line {
	ll a, b;
	Line(ll a = 0, ll b = 0) : a(a), b(b) {}
	bool operator<= (const Line& i) const { return (__int128_t)a * i.b <= (__int128_t)i.a * b; }
};
ll F(const Line& i, ll a) { return i.a * a + i.b; }
Line C(const Line& a, const Line& b) { return { a.b - b.b, b.a - a.a }; }
struct CHT {
	vector<Line> S; int pos = 0;
	void Insert(Line l) {
        if(S.size() > pos && S.back().a == l.a){
            if(l.b < S.back().b) l = S.back(); // max: <=, min: >=
            S.pop_back();
        }
		while (S.size() > 1 && C(S.back(), l) <= C(S[S.size() - 2], S.back())) S.pop_back();
		S.push_back(l);
	}
    ll Query(ll x) {
		int lo = 0, hi = S.size();
		while (lo + 1 < hi) {
			const int mid = lo + hi >> 1;
			if (C(S[mid - 1], S[mid]) <= Line(x, 1)) hi = mid; 
			else lo = mid;
		}
		return F(S[lo], x);
	}
};

int N;
ll T[1000010],dp[1000010];

CHT ch[1000010];
int p[1000010];
int find(int x){ return x==p[x]?x:p[x]=find(p[x]); }
void merge(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return;
    for(auto i:ch[y].S) ch[x].Insert(i);
    p[y]=x;
}

priority_queue<ll,vector<ll>,greater<>> pq,dpq;
void add(ll x){ pq.push(x); }
void del(ll x){ dpq.push(x); }
ll get(){
    while(!pq.empty()&&!dpq.empty()&&pq.top()==dpq.top()){
        pq.pop();
        dpq.pop();
    }
    assert(!pq.empty());
    return pq.top();
}

void TESTCASE() {
    cin>>N;
    for(int i=1;i<=N;i++) cin>>T[i];
    vector<array<int,3>> st;
    int chCnt=0;
    for(int i=1;i<=N;i++){
        int t=chCnt++;
        p[t]=t;
        ch[t].Insert(Line((N-i+1),dp[i-1]));
        while(!st.empty()&&st.back()[0]<=T[i]){
            del(st.back()[2]);
            merge(st.back()[1],t);
            st.pop_back();
        }
        t=find(t);
        ll cand=ch[t].Query(T[i]);
        add(cand);
        st.push_back({T[i],t,cand});
        dp[i]=get();
    }
    cout<<dp[N];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T=1; //cin>>T;
    for (int tc=1;tc<=T;tc++) {
        TESTCASE();
    }
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'void TESTCASE()':
Discharging.cpp:78:26: warning: narrowing conversion of 'T[i]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   78 |         st.push_back({T[i],t,cand});
      |                       ~~~^
Discharging.cpp:78:30: warning: narrowing conversion of 'cand' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   78 |         st.push_back({T[i],t,cand});
      |                              ^~~~

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