Submission #90315

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

route

# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

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];
      }
}

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

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

      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: In function 'int main()':
route.cpp:31: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:34: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	376 KB	Output is correct
3	Correct	2 ms	408 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	556 KB	Output is correct
7	Correct	2 ms	556 KB	Output is correct
8	Correct	2 ms	560 KB	Output is correct
9	Correct	2 ms	560 KB	Output is correct
10	Correct	39 ms	7004 KB	Output is correct
11	Correct	41 ms	7004 KB	Output is correct
12	Correct	40 ms	7004 KB	Output is correct
13	Runtime error	483 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
14	Halted	0 ms	0 KB	-