Submission #90307

#	Time	Username	Problem	Language	Result	Execution time	Memory
90307		mirbek01	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2 ms	476 KiB

route

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int N = 1e6 + 2;

int n, k, a[N], p[N], sz[N], L[N], bg, cur;
set < pair <int, int> >  s;

int f_s(int v){
      if(v < 1){
            v = n;
      }
      if(v > n){
            v = 1;
      }
      return p[v] == v?v:p[v] = f_s(p[v]);
}

void u_s(int x, int y){
      x = f_s(x);
      y = f_s(y);
      if(x != y){
            p[x] = y;
            sz[y] += sz[x];
            L[y] = L[x];
      }
}

main(){
      scanf("%lld %lld", &n, &k);

      for(int i = 1; i <= n; i ++){
            scanf("%lld", a + i);
      }

      bool ok = 1;

      for(int i = 1; i <= n; i ++){
            if(a[i] != a[1])
                  ok = 0;
      }

      if(ok){
            puts("0");
            return 0;
      }

      if(n == 2){
           bg = abs(a[2] - a[1]);
           if(a[1] < a[2]){
                  a[1] += k;
                  a[1] = min(a[2], a[1]);
            } else {
                  a[2] += k;
                  a[2] = min(a[2], a[1]);
            }
            cur = abs(a[2] - a[1]);
            cout << bg - cur << endl;
            return 0;
      }

      for(int i = 1; i <= n; i ++){
            int nxt = i + 1;
            if(nxt > n)
                  nxt = 1;
            bg += abs(a[i] - a[nxt]);
            p[i] = i, sz[i] = 1;
            L[i] = i;
      }

      for(int i = 1; i <= n; i ++){
            int pre = i - 1;
            if(pre < 1)
                  pre = n;
            if(a[i] == a[pre])
                  u_s(pre, i);
      }

      for(int i = 1; i <= n; i ++)
            s.insert({sz[f_s(i)], f_s(i)});

      while(!s.empty() && k > 0){
            pair <int, int> p = *s.begin();
            s.erase(s.begin());
            int l = f_s(L[p.second] - 1), r = f_s(p.second + 1);
            if(a[l] <= a[p.second] || a[r] <= a[p.second])
                  continue;
            int mn = min(k / sz[p.second], min(a[l], a[r]) - a[p.second]);
            k -= mn * sz[p.second];
            a[p.second] += mn;
            int presz = sz[p.second];
            if(a[p.second] == a[l]){
                  u_s(l, p.second);
            }
            if(a[f_s(p.second)] == a[r]){
                  u_s(p.second, r);
            }
            if(sz[f_s(p.second)] != presz){
                  s.insert({sz[f_s(p.second)], f_s(p.second)});
            }
      }

      for(int i = 1; i <= n; i ++){
            a[i] = a[f_s(i)];
      }

      for(int i = 1; i <= n; i ++){
            int nxt = i + 1;
            if(nxt > n)
                  nxt = 1;
            cur += abs(a[i] - a[nxt]);
      }

      cout << bg - cur << endl;
}
/***
9 10
8 5 5 5 8 5 4 4 5
5 2
5 4 3 4 5
6
3 1 2 5 6 4
***/

Compilation message (stderr)

route.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
route.cpp: In function 'int main()':
route.cpp:33:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld %lld", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~
route.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", a + i);
             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100