제출 #489261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489261		SirCovidThe19th	등산 경로 (IZhO12_route)	C++17	0 / 100	16 ms	23788 KiB

route

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mx = 1e6 + 5;

template<int sz> struct segTree{
	int seg[sz * 2 + 5];
	
	void upd(int i, int num){
    	seg[i += sz] = num;
    	for (i /= 2; i > 0; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
	}
	int query(int l, int r){ 
    	int ans = 0;
    	for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
        	if (l % 2 == 1) ans = max(ans, seg[l++]);
        	if (r % 2 == 0) ans = max(seg[r--], ans);
    	}
		return ans;
	}
};segTree<mx> st;

int n, k, A[mx], ans; vector<int> range[mx]; stack<int> stk; 

signed main(){
    cin >> n >> k;
    for (int iter = 0; iter <= 1; iter++){
        for (int i = 1; i <= n; i++){
            if (!iter) cin >> A[i], st.upd(i, A[i]); 
            while (!stk.empty()){
                int L = stk.top();
                if (!iter){
					int mxTop = st.query(L + 1, i - 1);
                    range[i - L - 1].push_back(min(A[L], A[i]) - mxTop);
                }
                else{
					int mxTop = max(st.query(1, i - 1), st.query(L + 1, n));
                    range[n - (L - i + 1)].push_back(min(A[L], A[i]) - mxTop);
                }
                if (A[L] > A[i]) break;
                stk.pop();
            }
            if (!iter) stk.push(i); 
        }
    }
    for (long long len = 1; len <= n; len++){
        for (int lim : range[len]){
            if (len * lim >= k) ans += 2 * (k / len), k = 0;
            else ans += 2 * lim, k -= len * lim;
        }
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 100