Submission #58123

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58123	2018-07-16T21:58:35 Z	Benq	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	377 ms	57688 KB

route

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1000001;

int N;
int par[MX], L[MX], R[MX], h[MX];

int norm(int x) { return (x%N+N)%N; }

int get(int x) {
    if (par[x] != x) par[x] = get(par[x]);
    return par[x];
}

pi tri(int x) {
    x = get(norm(x));
    return {h[x],x};
}

void uniteLeft(int a, int b) {
    R[a] = R[b];
    par[b] = a;
}

void uniteRight(int a, int b) {
    L[a] = L[b];
    par[b] = a;
}

int mag(int a, int b) {
    if (b < a) b += N;
    return b-a+1;
}

int k,ans, posi[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> k;
    F0R(i,N) {
        cin >> h[i];
        L[i] = R[i] = par[i] = i;
    }
    vi v(N); F0R(i,N) v[i] = i;
    sort(all(v),[](int a, int b) { if (h[a] != h[b]) return h[a] < h[b]; return a < b; });
    F0R(i,sz(v)-1) {
        auto a = v[i];
        // cout << a.f << " " << a.s << " " << L[a.s] << " " << R[a.s] << " " << mag(L[a.s],R[a.s]) << "\n";
        pi z1 = tri(L[a]-1);
        pi z2 = tri(R[a]+1);
        int m = mag(L[a],R[a]);
        if (z1 < z2) {
            posi[m] += z1.f-h[a];
            uniteLeft(z1.s,a);
        } else {
            posi[m] += z2.f-h[a];
            uniteRight(z2.s,a);
        }
        posi[m] = min(posi[m],MOD);
    }
    
    FOR(i,1,N) {
        int K = min(k/i,posi[i]);
        ans += K; k -= i*K;
    }
    cout << 2*ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	2 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	3 ms	628 KB	Output is correct
9	Correct	3 ms	628 KB	Output is correct
10	Correct	28 ms	2900 KB	Output is correct
11	Correct	48 ms	2900 KB	Output is correct
12	Correct	40 ms	3796 KB	Output is correct
13	Correct	377 ms	26052 KB	Output is correct
14	Correct	254 ms	26108 KB	Output is correct
15	Correct	253 ms	26108 KB	Output is correct
16	Correct	249 ms	26156 KB	Output is correct
17	Correct	292 ms	34744 KB	Output is correct
18	Correct	245 ms	44056 KB	Output is correct
19	Correct	291 ms	53964 KB	Output is correct
20	Correct	192 ms	57688 KB	Output is correct