Submission #90310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90310	2018-12-21T08:29:14 Z	mirbek01	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	330 ms	66560 KB

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]){
                  s.erase({sz[l], l});
                  u_s(l, p.second);
            }
            if(a[f_s(p.second)] == a[r]){
                  s.erase({sz[r], 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;
}

Compilation message

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	1 ms	376 KB	Output is correct
3	Correct	2 ms	576 KB	Output is correct
4	Correct	2 ms	576 KB	Output is correct
5	Correct	2 ms	576 KB	Output is correct
6	Correct	2 ms	696 KB	Output is correct
7	Correct	2 ms	696 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	2 ms	764 KB	Output is correct
10	Correct	45 ms	10916 KB	Output is correct
11	Correct	47 ms	11912 KB	Output is correct
12	Correct	32 ms	11912 KB	Output is correct
13	Runtime error	330 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-