oj.uz

Submission #1114387

# Submission time Handle Problem Language Result Execution time Memory
1114387 2024-11-18T18:27:29 Z duckindog Line Town (CCO23_day1problem3) C++17
4 / 25
 2000 ms 31888 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;
        memset(T.bit, 0, sizeof T.bit);
        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) 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 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 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 12 ms 17656 KB Output is correct
2 Correct 12 ms 17744 KB Output is correct
3 Correct 534 ms 17856 KB Output is correct
4 Correct 516 ms 17744 KB Output is correct
5 Correct 645 ms 17840 KB Output is correct
6 Correct 619 ms 17744 KB Output is correct
7 Correct 541 ms 17744 KB Output is correct
8 Correct 661 ms 17744 KB Output is correct
9 Correct 8 ms 17744 KB Output is correct
10 Correct 10 ms 17752 KB Output is correct
11 Correct 637 ms 17864 KB Output is correct
12 Correct 538 ms 17744 KB Output is correct
13 Correct 647 ms 17744 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17656 KB Output is correct
2 Correct 12 ms 17744 KB Output is correct
3 Correct 534 ms 17856 KB Output is correct
4 Correct 516 ms 17744 KB Output is correct
5 Correct 645 ms 17840 KB Output is correct
6 Correct 619 ms 17744 KB Output is correct
7 Correct 541 ms 17744 KB Output is correct
8 Correct 661 ms 17744 KB Output is correct
9 Correct 8 ms 17744 KB Output is correct
10 Correct 10 ms 17752 KB Output is correct
11 Correct 637 ms 17864 KB Output is correct
12 Correct 538 ms 17744 KB Output is correct
13 Correct 647 ms 17744 KB Output is correct
14 Execution timed out 2027 ms 31888 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17744 KB Output is correct
2 Correct 9 ms 17744 KB Output is correct
3 Correct 9 ms 17744 KB Output is correct
4 Incorrect 10 ms 17744 KB Output isn't correct
5 Halted 0 ms 0 KB -