Submission #489264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
489264	2021-11-21T19:53:26 Z	SirCovidThe19th	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	507 ms	65540 KB

route

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

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; 

int 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);
					//cout<<L<<" "<<i<<" "<<min(A[L], A[i]) - mxTop<<endl;
                }
                else{
					int mxTop = max(st.query(1, i - 1), st.query(L + 1, n));
					if (mxTop > min(A[L], A[i])) break;
                    range[n - (L - i + 1)].push_back(min(A[L], A[i]) - mxTop);
					//cout<<i<<" "<<L<<" "<<min(A[L], A[i]) - mxTop<<endl;
                }
                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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23780 KB	Output is correct
2	Correct	13 ms	23756 KB	Output is correct
3	Correct	14 ms	23756 KB	Output is correct
4	Correct	14 ms	23788 KB	Output is correct
5	Correct	13 ms	23804 KB	Output is correct
6	Correct	13 ms	23760 KB	Output is correct
7	Correct	12 ms	23992 KB	Output is correct
8	Correct	13 ms	23888 KB	Output is correct
9	Correct	14 ms	23796 KB	Output is correct
10	Correct	62 ms	29404 KB	Output is correct
11	Correct	62 ms	26996 KB	Output is correct
12	Correct	63 ms	29352 KB	Output is correct
13	Runtime error	507 ms	65540 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-