Submission #90348

#	Time	Username	Problem	Language	Result	Execution time	Memory
90348		mirbek01	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2 ms	256 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, used[N];
priority_queue < pair <int, int> >  s;

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

int main(){
      freopen("3.in", "r", stdin);
      freopen("out.txt", "w", stdout);

      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 ++){
            s.push({-sz[f_s(i)], f_s(i)});
      }

      while(!s.empty() && k > 0){
            pair <int, int> p = s.top();
            s.pop();
            if(used[p.second])
                  continue;
            used[p.second] = 1;
            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]){
                  used[l] = 1;
                  u_s(l, p.second);
            }
            if(a[p.second] == a[r]){
                  used[r] = 1;
                  u_s(p.second, r);
            }
            if(sz[f_s(p.second)] != presz){
                  s.push({-sz[f_s(p.second)], f_s(p.second)});
                  used[f_s(p.second)] = 0;
            }
      }

      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:31:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
       freopen("3.in", "r", stdin);
       ~~~~~~~^~~~~~~~~~~~~~~~~~~~
route.cpp:32:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
       freopen("out.txt", "w", stdout);
       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
route.cpp:34: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:37: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