Submission #340882

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340882	2020-12-28T12:59:11 Z	talant117408	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	419 ms	65536 KB

route

/*
    Code written by Talant I.D.
*/
  
#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link, lborder;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); lborder.resize(n);
            iota(all(link), 0); iota(all(lborder), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int n;

int Mode(int x){
    if(x < 0) x += n;
    if(x > n-1) x -= n;
    return x;
}

int main(){
    do_not_disturb
    
    int k;
    cin >> n >> k;
    Union mountain(n);
    vector <int> v(n);
    for(auto &to : v) cin >> to;
    for(int i = 0; i < n; i++){
        if(v[i] == v[Mode(i+1)]){
            mountain.unite(i, Mode(i+1));
        }
    }
    
    set <pii> st;
    for(int i = 0; i < n; i++){
        st.insert(mp(mountain.getsize(i), mountain.find(i)));
    }
    
    priority_queue <pii> K;
    for(auto to : st)
        if(v[to.second] < min(v[Mode(to.second-1)], v[Mode(to.second+to.first)]))
            K.push(mp(-to.first, to.second));
    
    int ans = 0;
    
    while(k && sz(K)){
        auto it = K.top(); K.pop();
        it.first = abs(it.first);
        if(it.first == n) break;
        
        int needed = min(v[Mode(it.second-1)]-v[it.second], v[Mode(it.second+it.first)]-v[it.second]);
        if(needed*it.first > k){
            ans += k/it.first*2;
            break;
        }
        else{
            ans += needed*2;
            k -= needed*it.first;
        }
        if(v[Mode(it.second-1)] == min(v[Mode(it.second-1)], v[Mode(it.second+it.first)])){
            mountain.unite(Mode(it.second-1), it.second);
            if(v[Mode(it.second+it.first)] == min(v[Mode(it.second-1)], v[Mode(it.second+it.first)])){
                mountain.unite(Mode(it.second-1), Mode(it.second+it.first));
            }
        }
        else{
            if(v[(it.second+it.first)%n] == min(v[Mode(it.second-1)], v[Mode(it.second+it.first)])){
                mountain.unite(it.second, Mode(it.second+it.first));
                v[it.second] = v[Mode(it.second+it.first)]; 
            }
        }
        it.second = mountain.find(it.second);
        it.first = mountain.getsize(it.second);
        if(v[it.second] < min(v[Mode(it.second-1)], v[Mode(it.second+it.first)]))
            K.push(mp(-it.first, mountain.find(it.second)));
    }
    
    cout << ans ;
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	33 ms	7404 KB	Output is correct
11	Correct	38 ms	8168 KB	Output is correct
12	Correct	23 ms	5100 KB	Output is correct
13	Correct	419 ms	65536 KB	Output is correct
14	Correct	387 ms	65536 KB	Output is correct
15	Correct	375 ms	65536 KB	Output is correct
16	Correct	377 ms	65536 KB	Output is correct
17	Correct	381 ms	65536 KB	Output is correct
18	Correct	380 ms	65536 KB	Output is correct
19	Correct	382 ms	65536 KB	Output is correct
20	Correct	236 ms	45292 KB	Output is correct