Submission #1114495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114495		duckindog	Line Town (CCO23_day1problem3)	C++17	25 / 25	471 ms	53524 KiB

Main

#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 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 3 / 3
• Subtask 7: 2 / 2
• Subtask 8: 3 / 3