답안 #90357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90357	2018-12-21T10:33:23 Z	mirbek01	등산 경로 (IZhO12_route)	C++17	0 / 100	545 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	392 KB	Output is correct
5	Correct	2 ms	392 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	548 KB	Output is correct
8	Correct	2 ms	548 KB	Output is correct
9	Correct	2 ms	548 KB	Output is correct
10	Correct	48 ms	4640 KB	Output is correct
11	Correct	39 ms	4640 KB	Output is correct
12	Correct	42 ms	5100 KB	Output is correct
13	Correct	532 ms	37144 KB	Output is correct
14	Correct	545 ms	43340 KB	Output is correct
15	Correct	529 ms	51020 KB	Output is correct
16	Correct	525 ms	59856 KB	Output is correct
17	Runtime error	541 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.
18	Halted	0 ms	0 KB	-