oj.uz

Submission #1114495

# Submission time Handle Problem Language Result Execution time Memory
1114495 2024-11-19T06:17:21 Z duckindog Line Town (CCO23_day1problem3) C++17
25 / 25
 471 ms 53524 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int N = 500'000 + 10,
          MAX = 1'000'000'000'000'000;
int n;
int h[N];

struct BIT { 
  int bit[N];
  void upd(int i, int x) { 
    for (; i <= n; i += i & -i) bit[i] += x;
  }
  void assign(int i) { 
    for (; i <= n; i += i & -i) bit[i] = 0;
  }
  int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += bit[i];
    return ret;
  }
} T, Z, P;

int a[N], pref[N];
int f[N][2];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];

  vector<int> allValue(n); iota(allValue.begin(), allValue.end(), 1);
  sort(allValue.begin(), allValue.end(), [&](const auto& a, const auto& b) { 
    return make_pair(abs(h[a]), -a) > make_pair(abs(h[b]), -b);
  });

  for (int i = 1; i <= n; ++i) Z.upd(i, 1), P.upd(i, 1);

  memset(f, 14, sizeof f);
  f[0][0] = 0;

  int totalSize = 0;
  for (int le = 0; le < (int)allValue.size(); ++le) { 
    int ri = le;
    while (ri < (int)allValue.size() && 
            abs(h[allValue[le]]) == abs(h[allValue[ri]])) ri += 1;
    
    vector<int> vt(allValue.begin() + le, allValue.begin() + ri);
    vt.insert(vt.begin(), 0);
    
    const int sz = vt.size() - 1;
    totalSize += sz;

    for (int i = 1; i <= sz; ++i) { 
      Z.upd(vt[i], -1);
      a[i] = h[vt[i]] > 0 ? 1 : h[vt[i]] < 0 ? -1 : 0;
    }
    const int cntZero = Z.que(n);
    
    int totalZero = 0;
    for (int i = 1; i <= sz; ++i) totalZero += cntZero - Z.que(vt[i]);
    
    for (int l = 0; l <= 1; ++l) { 
      for (int type = 0; type <= 1; ++type) { 
        array<deque<int>, 2> q;
        for (int i = 1; i <= sz; ++i) {
          q[(vt[i] ^ (a[i] == 1)) & 1].push_back(vt[i]);
          pref[i] = MAX;
        }
        int preL = (l ^ (sz ^ type)) & 1;
        
        vector<int> sequence;
        for (int i = 1; i < sz; ++i) { 
          auto& ret = pref[i];
          ret = pref[i - 1];

          int which = (i ^ preL) & 1;
          if (!q[which].size()) ret = MAX;
          else { 
            int pos = q[which].front(); q[which].pop_front();
            ret += P.que(pos) - 1 - T.que(pos - 1);
            ret -= cntZero - Z.que(pos);

            T.upd(pos, 1);
            
            sequence.push_back(pos);
          }
        }

        int total = totalZero;
        if (!type) { 
          int i = sz;
          auto& ret = pref[i];
          ret = pref[i - 1];

          int which = (i ^ preL) & 1;

          if (!q[which].size()) ret = MAX;
          else { 
            int pos = q[which].front(); q[which].pop_front();
            ret += P.que(pos) - 1 - T.que(pos - 1);
            ret -= cntZero - Z.que(pos);
            T.upd(pos, 1);

            sequence.push_back(pos);
          }
        } else { 
          int which = (n ^ totalSize ^ l) & 1;
          if (!q[which].size()) total = MAX;
          else { 
            int pos = q[which].front(); q[which].pop_front();
            total += P.que(pos) - 1 - T.que(pos - 1) - Z.que(pos - 1);

            sequence.push_back(pos);
          }
        }
        
        int value = MAX;
        if ((int)sequence.size() == sz) { 
          value = min(value, pref[sz - type] + total);
          
          for (int i = sz - (!type ? 1 : 2); i >= 1; i -= 2) { 
            if (!(cntZero & 1)) swap(sequence[i - 1], sequence[i]);
            
            int pos0 = sequence[i - 1], pos1 = sequence[i];
            T.upd(pos0, -1);
            T.upd(pos1, -1);
    
            total += P.que(pos0) - 1 - T.que(pos0 - 1) - Z.que(pos0 - 1);
            T.upd(pos0, 1);
            total += P.que(pos1) - 1 - T.que(pos1 - 1) - Z.que(pos1 - 1);
            T.upd(pos1, 1);
    
            T.upd(pos0, -1);
            T.upd(pos1, -1);

            value = min(value, pref[i - 1] + total);
          }
        }
        
        auto& ret = f[totalSize][l];
        if (!h[vt[1]]) ret = min(ret, f[totalSize - sz][l]);
        else ret = min(ret, f[totalSize - sz][preL] + value);

        for (int i = 1; i <= sz; ++i) T.assign(vt[i]);    
      }
    }
    for (int i = 1; i <= sz; ++i) P.upd(vt[i], -1);

    le = ri - 1;
  }

  int answer = min(f[totalSize][0], f[totalSize][1]);
  cout << (answer >= MAX ? -1 : answer) << "\n";
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 217 ms 53264 KB Output is correct
16 Correct 222 ms 53248 KB Output is correct
17 Correct 221 ms 53244 KB Output is correct
18 Correct 185 ms 53248 KB Output is correct
19 Correct 245 ms 53352 KB Output is correct
20 Correct 281 ms 53248 KB Output is correct
21 Correct 254 ms 53252 KB Output is correct
22 Correct 297 ms 53252 KB Output is correct
23 Correct 302 ms 53368 KB Output is correct
24 Correct 242 ms 53248 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct
14 Correct 3 ms 16976 KB Output is correct
15 Correct 3 ms 19192 KB Output is correct
16 Correct 4 ms 19024 KB Output is correct
17 Correct 3 ms 17148 KB Output is correct
18 Correct 4 ms 16976 KB Output is correct
19 Correct 3 ms 19160 KB Output is correct
20 Correct 3 ms 16976 KB Output is correct
21 Correct 4 ms 19024 KB Output is correct
22 Correct 3 ms 19024 KB Output is correct
23 Correct 4 ms 16976 KB Output is correct
24 Correct 3 ms 16976 KB Output is correct
25 Correct 3 ms 16976 KB Output is correct
26 Correct 3 ms 19024 KB Output is correct
27 Correct 3 ms 19024 KB Output is correct
28 Correct 4 ms 16976 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 3 ms 19024 KB Output is correct
31 Correct 3 ms 16976 KB Output is correct
32 Correct 3 ms 16976 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 217 ms 53264 KB Output is correct
16 Correct 222 ms 53248 KB Output is correct
17 Correct 221 ms 53244 KB Output is correct
18 Correct 185 ms 53248 KB Output is correct
19 Correct 245 ms 53352 KB Output is correct
20 Correct 281 ms 53248 KB Output is correct
21 Correct 254 ms 53252 KB Output is correct
22 Correct 297 ms 53252 KB Output is correct
23 Correct 302 ms 53368 KB Output is correct
24 Correct 242 ms 53248 KB Output is correct
25 Correct 3 ms 16976 KB Output is correct
26 Correct 3 ms 19192 KB Output is correct
27 Correct 4 ms 19024 KB Output is correct
28 Correct 3 ms 17148 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 3 ms 19160 KB Output is correct
31 Correct 3 ms 16976 KB Output is correct
32 Correct 4 ms 19024 KB Output is correct
33 Correct 3 ms 19024 KB Output is correct
34 Correct 4 ms 16976 KB Output is correct
35 Correct 3 ms 16976 KB Output is correct
36 Correct 3 ms 16976 KB Output is correct
37 Correct 3 ms 19024 KB Output is correct
38 Correct 3 ms 19024 KB Output is correct
39 Correct 4 ms 16976 KB Output is correct
40 Correct 4 ms 16976 KB Output is correct
41 Correct 3 ms 19024 KB Output is correct
42 Correct 3 ms 16976 KB Output is correct
43 Correct 3 ms 16976 KB Output is correct
44 Correct 262 ms 46372 KB Output is correct
45 Correct 279 ms 46884 KB Output is correct
46 Correct 247 ms 47136 KB Output is correct
47 Correct 245 ms 46632 KB Output is correct
48 Correct 325 ms 52004 KB Output is correct
49 Correct 312 ms 53256 KB Output is correct
50 Correct 257 ms 46880 KB Output is correct
51 Correct 249 ms 47532 KB Output is correct
52 Correct 251 ms 47656 KB Output is correct
53 Correct 207 ms 46376 KB Output is correct
54 Correct 347 ms 50380 KB Output is correct
55 Correct 263 ms 50376 KB Output is correct
56 Correct 274 ms 51732 KB Output is correct
57 Correct 230 ms 52996 KB Output is correct
58 Correct 246 ms 53004 KB Output is correct
59 Correct 219 ms 53000 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 3 ms 19088 KB Output is correct
3 Correct 4 ms 19024 KB Output is correct
4 Correct 4 ms 19024 KB Output is correct
5 Correct 4 ms 19116 KB Output is correct
6 Correct 4 ms 19024 KB Output is correct
7 Correct 5 ms 19024 KB Output is correct
8 Correct 3 ms 18912 KB Output is correct
9 Correct 3 ms 19024 KB Output is correct
10 Correct 2 ms 19024 KB Output is correct
11 Correct 4 ms 18924 KB Output is correct
12 Correct 4 ms 19024 KB Output is correct
13 Correct 4 ms 19024 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 3 ms 19088 KB Output is correct
3 Correct 4 ms 19024 KB Output is correct
4 Correct 4 ms 19024 KB Output is correct
5 Correct 4 ms 19116 KB Output is correct
6 Correct 4 ms 19024 KB Output is correct
7 Correct 5 ms 19024 KB Output is correct
8 Correct 3 ms 18912 KB Output is correct
9 Correct 3 ms 19024 KB Output is correct
10 Correct 2 ms 19024 KB Output is correct
11 Correct 4 ms 18924 KB Output is correct
12 Correct 4 ms 19024 KB Output is correct
13 Correct 4 ms 19024 KB Output is correct
14 Correct 287 ms 36440 KB Output is correct
15 Correct 393 ms 36552 KB Output is correct
16 Correct 387 ms 34884 KB Output is correct
17 Correct 394 ms 34888 KB Output is correct
18 Correct 428 ms 35012 KB Output is correct
19 Correct 441 ms 35656 KB Output is correct
20 Correct 3 ms 19024 KB Output is correct
21 Correct 2 ms 16976 KB Output is correct
22 Correct 335 ms 36536 KB Output is correct
23 Correct 327 ms 36540 KB Output is correct
24 Correct 266 ms 34632 KB Output is correct

Subtask #7
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct
14 Correct 3 ms 16976 KB Output is correct
15 Correct 3 ms 19192 KB Output is correct
16 Correct 4 ms 19024 KB Output is correct
17 Correct 3 ms 17148 KB Output is correct
18 Correct 4 ms 16976 KB Output is correct
19 Correct 3 ms 19160 KB Output is correct
20 Correct 3 ms 16976 KB Output is correct
21 Correct 4 ms 19024 KB Output is correct
22 Correct 3 ms 19024 KB Output is correct
23 Correct 4 ms 16976 KB Output is correct
24 Correct 3 ms 16976 KB Output is correct
25 Correct 3 ms 16976 KB Output is correct
26 Correct 3 ms 19024 KB Output is correct
27 Correct 3 ms 19024 KB Output is correct
28 Correct 4 ms 16976 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 3 ms 19024 KB Output is correct
31 Correct 3 ms 16976 KB Output is correct
32 Correct 3 ms 16976 KB Output is correct
33 Correct 3 ms 19024 KB Output is correct
34 Correct 3 ms 19088 KB Output is correct
35 Correct 4 ms 19024 KB Output is correct
36 Correct 4 ms 19024 KB Output is correct
37 Correct 4 ms 19116 KB Output is correct
38 Correct 4 ms 19024 KB Output is correct
39 Correct 5 ms 19024 KB Output is correct
40 Correct 3 ms 18912 KB Output is correct
41 Correct 3 ms 19024 KB Output is correct
42 Correct 2 ms 19024 KB Output is correct
43 Correct 4 ms 18924 KB Output is correct
44 Correct 4 ms 19024 KB Output is correct
45 Correct 4 ms 19024 KB Output is correct
46 Correct 4 ms 16976 KB Output is correct
47 Correct 4 ms 19024 KB Output is correct
48 Correct 4 ms 19024 KB Output is correct
49 Correct 4 ms 17144 KB Output is correct
50 Correct 3 ms 16976 KB Output is correct
51 Correct 3 ms 17144 KB Output is correct
52 Correct 3 ms 19024 KB Output is correct
53 Correct 4 ms 16976 KB Output is correct
54 Correct 3 ms 19024 KB Output is correct
55 Correct 3 ms 16976 KB Output is correct
56 Correct 3 ms 16976 KB Output is correct
57 Correct 3 ms 19192 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 19024 KB Output is correct
4 Correct 3 ms 16976 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 16976 KB Output is correct
7 Correct 3 ms 19024 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 4 ms 19196 KB Output is correct
10 Correct 4 ms 16976 KB Output is correct
11 Correct 3 ms 19024 KB Output is correct
12 Correct 3 ms 19024 KB Output is correct
13 Correct 3 ms 17144 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 217 ms 53264 KB Output is correct
16 Correct 222 ms 53248 KB Output is correct
17 Correct 221 ms 53244 KB Output is correct
18 Correct 185 ms 53248 KB Output is correct
19 Correct 245 ms 53352 KB Output is correct
20 Correct 281 ms 53248 KB Output is correct
21 Correct 254 ms 53252 KB Output is correct
22 Correct 297 ms 53252 KB Output is correct
23 Correct 302 ms 53368 KB Output is correct
24 Correct 242 ms 53248 KB Output is correct
25 Correct 3 ms 16976 KB Output is correct
26 Correct 3 ms 19192 KB Output is correct
27 Correct 4 ms 19024 KB Output is correct
28 Correct 3 ms 17148 KB Output is correct
29 Correct 4 ms 16976 KB Output is correct
30 Correct 3 ms 19160 KB Output is correct
31 Correct 3 ms 16976 KB Output is correct
32 Correct 4 ms 19024 KB Output is correct
33 Correct 3 ms 19024 KB Output is correct
34 Correct 4 ms 16976 KB Output is correct
35 Correct 3 ms 16976 KB Output is correct
36 Correct 3 ms 16976 KB Output is correct
37 Correct 3 ms 19024 KB Output is correct
38 Correct 3 ms 19024 KB Output is correct
39 Correct 4 ms 16976 KB Output is correct
40 Correct 4 ms 16976 KB Output is correct
41 Correct 3 ms 19024 KB Output is correct
42 Correct 3 ms 16976 KB Output is correct
43 Correct 3 ms 16976 KB Output is correct
44 Correct 262 ms 46372 KB Output is correct
45 Correct 279 ms 46884 KB Output is correct
46 Correct 247 ms 47136 KB Output is correct
47 Correct 245 ms 46632 KB Output is correct
48 Correct 325 ms 52004 KB Output is correct
49 Correct 312 ms 53256 KB Output is correct
50 Correct 257 ms 46880 KB Output is correct
51 Correct 249 ms 47532 KB Output is correct
52 Correct 251 ms 47656 KB Output is correct
53 Correct 207 ms 46376 KB Output is correct
54 Correct 347 ms 50380 KB Output is correct
55 Correct 263 ms 50376 KB Output is correct
56 Correct 274 ms 51732 KB Output is correct
57 Correct 230 ms 52996 KB Output is correct
58 Correct 246 ms 53004 KB Output is correct
59 Correct 219 ms 53000 KB Output is correct
60 Correct 3 ms 19024 KB Output is correct
61 Correct 3 ms 19088 KB Output is correct
62 Correct 4 ms 19024 KB Output is correct
63 Correct 4 ms 19024 KB Output is correct
64 Correct 4 ms 19116 KB Output is correct
65 Correct 4 ms 19024 KB Output is correct
66 Correct 5 ms 19024 KB Output is correct
67 Correct 3 ms 18912 KB Output is correct
68 Correct 3 ms 19024 KB Output is correct
69 Correct 2 ms 19024 KB Output is correct
70 Correct 4 ms 18924 KB Output is correct
71 Correct 4 ms 19024 KB Output is correct
72 Correct 4 ms 19024 KB Output is correct
73 Correct 287 ms 36440 KB Output is correct
74 Correct 393 ms 36552 KB Output is correct
75 Correct 387 ms 34884 KB Output is correct
76 Correct 394 ms 34888 KB Output is correct
77 Correct 428 ms 35012 KB Output is correct
78 Correct 441 ms 35656 KB Output is correct
79 Correct 3 ms 19024 KB Output is correct
80 Correct 2 ms 16976 KB Output is correct
81 Correct 335 ms 36536 KB Output is correct
82 Correct 327 ms 36540 KB Output is correct
83 Correct 266 ms 34632 KB Output is correct
84 Correct 4 ms 16976 KB Output is correct
85 Correct 4 ms 19024 KB Output is correct
86 Correct 4 ms 19024 KB Output is correct
87 Correct 4 ms 17144 KB Output is correct
88 Correct 3 ms 16976 KB Output is correct
89 Correct 3 ms 17144 KB Output is correct
90 Correct 3 ms 19024 KB Output is correct
91 Correct 4 ms 16976 KB Output is correct
92 Correct 3 ms 19024 KB Output is correct
93 Correct 3 ms 16976 KB Output is correct
94 Correct 3 ms 16976 KB Output is correct
95 Correct 3 ms 19192 KB Output is correct
96 Correct 298 ms 44360 KB Output is correct
97 Correct 316 ms 44196 KB Output is correct
98 Correct 272 ms 44376 KB Output is correct
99 Correct 367 ms 34888 KB Output is correct
100 Correct 280 ms 53524 KB Output is correct
101 Correct 440 ms 36412 KB Output is correct
102 Correct 402 ms 36424 KB Output is correct
103 Correct 471 ms 34888 KB Output is correct
104 Correct 423 ms 34172 KB Output is correct
105 Correct 389 ms 33516 KB Output is correct
106 Correct 379 ms 33584 KB Output is correct