Submission #90389

#	Time	Username	Problem	Language	Result	Execution time	Memory
90389		mirbek01	Mountain Trek Route (IZhO12_route)	C++11	100 / 100	538 ms	38908 KiB

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 (stderr)

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 / 100