Submission #340883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340883	2020-12-28T12:59:49 Z	talant117408	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	388 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	0 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	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	0 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	32 ms	6784 KB	Output is correct
11	Correct	38 ms	7272 KB	Output is correct
12	Correct	23 ms	4204 KB	Output is correct
13	Correct	388 ms	65536 KB	Output is correct
14	Correct	377 ms	65536 KB	Output is correct
15	Correct	371 ms	65536 KB	Output is correct
16	Correct	372 ms	65536 KB	Output is correct
17	Correct	376 ms	65536 KB	Output is correct
18	Correct	378 ms	65536 KB	Output is correct
19	Correct	384 ms	65536 KB	Output is correct
20	Correct	238 ms	39532 KB	Output is correct