Submission #90389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90389	2018-12-21T13:12:01 Z	mirbek01	Mountain Trek Route (IZhO12_route)	C++11	100 / 100	538 ms	38908 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

100.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	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	592 KB	Output is correct
7	Correct	2 ms	592 KB	Output is correct
8	Correct	2 ms	616 KB	Output is correct
9	Correct	2 ms	668 KB	Output is correct
10	Correct	52 ms	4580 KB	Output is correct
11	Correct	41 ms	4600 KB	Output is correct
12	Correct	43 ms	4964 KB	Output is correct
13	Correct	538 ms	38800 KB	Output is correct
14	Correct	533 ms	38908 KB	Output is correct
15	Correct	513 ms	38908 KB	Output is correct
16	Correct	525 ms	38908 KB	Output is correct
17	Correct	529 ms	38908 KB	Output is correct
18	Correct	514 ms	38908 KB	Output is correct
19	Correct	519 ms	38908 KB	Output is correct
20	Correct	422 ms	38908 KB	Output is correct