Submission #90296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90296	2018-12-21T07:12:19 Z	mirbek01	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2 ms	500 KB

route

# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;

int n, k, a[N], p[N], sz[N], L[N], R[N];
long long bg = 0, cur = 0;
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];
            a[y] = max(a[x], a[y]);
      }
}

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

      for(int i = 1; i <= n; i ++){
            scanf("%d", 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){
            assert(0);
           if(a[1] < a[2]){
                  a[1] += k;
                  a[1] = min(a[2], a[1]);
                  cout << abs(a[1] - a[2]) * 2 << endl;
            } else {
                  a[2] += k;
                  a[2] = min(a[2], a[1]);
                  cout << abs(a[1] - a[2]) * 2 << 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, R[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(R[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 2
5 4 4 4 5 8 5 5 8
***/

Compilation message

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("%d %d", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~
route.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a + i);
             ~~~~~^~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Incorrect	2 ms	500 KB	Output isn't correct
4	Halted	0 ms	0 KB	-