oj.uz

Submission #1114388

# Submission time Handle Problem Language Result Execution time Memory
1114388 2024-11-18T18:30:54 Z duckindog Line Town (CCO23_day1problem3) C++17
7 / 25
 532 ms 32840 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 abs(h[a]) > abs(h[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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14416 KB Output is correct
2 Correct 4 ms 14416 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 7 ms 14336 KB Output is correct
8 Correct 7 ms 14444 KB Output is correct
9 Correct 6 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Correct 9 ms 14416 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14416 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14416 KB Output is correct
2 Correct 4 ms 14416 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 7 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 7 ms 14336 KB Output is correct
8 Correct 7 ms 14444 KB Output is correct
9 Correct 6 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Correct 9 ms 14416 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14416 KB Output is correct
14 Correct 450 ms 27776 KB Output is correct
15 Correct 481 ms 32840 KB Output is correct
16 Correct 484 ms 29704 KB Output is correct
17 Correct 532 ms 29768 KB Output is correct
18 Correct 466 ms 27720 KB Output is correct
19 Correct 532 ms 29912 KB Output is correct
20 Correct 3 ms 14416 KB Output is correct
21 Correct 3 ms 14416 KB Output is correct
22 Correct 366 ms 30460 KB Output is correct
23 Correct 341 ms 30668 KB Output is correct
24 Correct 326 ms 29512 KB Output is correct

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14416 KB Output is correct
2 Correct 5 ms 14416 KB Output is correct
3 Correct 5 ms 14588 KB Output is correct
4 Incorrect 7 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -