Submission #90388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90388	2018-12-21T13:11:28 Z	mirbek01	Mountain Trek Route (IZhO12_route)	C++14	0 / 100	540 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], R[N], bg, cur;
pair <int, int> t[N * 4];

int f_s(int v){
      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){
            if(sz[y] < sz[x]){
                  sz[x] += sz[y];
                  p[y] = x;
                  R[x] = R[y];
            } else {
                  sz[y] += sz[x];
                  p[x] = y;
                  L[y] = L[x];
            }
      }
}

void update(int pos, int val, int v = 1, int tl = 1, int tr = n){
      if(tl == tr)
            t[v] = {val, tl};
      else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  update(pos, val, v << 1, tl, tm);
            else
                  update(pos, val, (v << 1) | 1, tm + 1, tr);
            t[v] = min(t[v << 1], t[(v << 1) | 1]);
      }
}

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;
            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 ++)
            update(i, 1e9);

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

      while(k > 0){
            pair <int, int> p = t[1];
            if(p.first == 1e9)
                  break;
            update(p.second, 1e9);
            int l = L[p.second] - 1, r = R[p.second] + 1;
            if(l < 1)
                  l = n;
            if(r > n)
                  r = 1;
            l = f_s(l);
            r = f_s(r);
            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]){
                  update(l, 1e9);
                  u_s(l, p.second);
            }
            if(a[f_s(p.second)] == a[r]){
                  update(r, 1e9);
                  u_s(p.second, r);
            }
            if(sz[f_s(p.second)] != presz){
                  update(f_s(p.second), sz[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:44: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:47: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	476 KB	Output is correct
4	Correct	2 ms	476 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	488 KB	Output is correct
7	Correct	2 ms	488 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	2 ms	696 KB	Output is correct
10	Correct	48 ms	4592 KB	Output is correct
11	Correct	40 ms	4592 KB	Output is correct
12	Correct	43 ms	5104 KB	Output is correct
13	Correct	532 ms	40352 KB	Output is correct
14	Correct	527 ms	43484 KB	Output is correct
15	Correct	525 ms	43728 KB	Output is correct
16	Correct	538 ms	43728 KB	Output is correct
17	Correct	526 ms	43728 KB	Output is correct
18	Correct	533 ms	53088 KB	Output is correct
19	Correct	540 ms	62624 KB	Output is correct
20	Runtime error	440 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.