Submission #58122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58122	2018-07-16T21:55:09 Z	Benq	Mountain Trek Route (IZhO12_route)	C++14	0 / 100	299 ms	66560 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;
}

ll 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;
    }
    vpi v; F0R(i,N) v.pb({h[i],i});
    sort(all(v));
    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.s]-1);
        pi z2 = tri(R[a.s]+1);
        if (z1 < z2) {
            posi[mag(L[a.s],R[a.s])] += z1.f-a.f;
            uniteLeft(z1.s,a.s);
        } else {
            posi[mag(L[a.s],R[a.s])] += z2.f-a.f;
            uniteRight(z2.s,a.s);
        }
    }
    
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	552 KB	Output is correct
3	Correct	2 ms	552 KB	Output is correct
4	Correct	2 ms	552 KB	Output is correct
5	Correct	2 ms	552 KB	Output is correct
6	Correct	2 ms	552 KB	Output is correct
7	Correct	2 ms	552 KB	Output is correct
8	Correct	3 ms	660 KB	Output is correct
9	Correct	2 ms	704 KB	Output is correct
10	Correct	28 ms	3780 KB	Output is correct
11	Correct	49 ms	3780 KB	Output is correct
12	Correct	41 ms	4732 KB	Output is correct
13	Correct	258 ms	42788 KB	Output is correct
14	Correct	254 ms	52188 KB	Output is correct
15	Correct	299 ms	59856 KB	Output is correct
16	Runtime error	231 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
17	Halted	0 ms	0 KB	-