답안 #90389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90389 2018-12-21T13:12:01 Z mirbek01 등산 경로 (IZhO12_route) C++11
100 / 100
538 ms 38908 KB
# 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);
             ~~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 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