Submission #1114223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114223		duckindog	Line Town (CCO23_day1problem3)	C++17	17 / 25	173 ms	102988 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];

namespace sub4 { 
  struct BIT { 
    int bit[N];
    inline void upd(int i, int x) { 
      for (; i <= n; i += i & -i) bit[i] += x;
    }
    inline int que(int i) { 
      int ret = 0;
      for (; i; i -= i & -i) ret += bit[i];
      return ret;
    }
  } T, Z;
  
  int pref[N];
  
  vector<int> position;
  void solve() { 
    int cntZero = 0, totalZero = 0;
    for (int i = 1; i <= n; ++i) {
      if (h[i]) continue;
      position.push_back(i);
      cntZero += 1;
      totalZero += i - 1 - Z.que(i - 1);
      Z.upd(i, 1);
    }
    const int sz = n - cntZero;
    
    int answer = MAX;
    for (int type = 1; type <= 2; ++type) { 
      memset(pref, 0, sizeof pref);
      memset(T.bit, 0, sizeof T.bit);
  
      deque<int> odd, even;
      for (int i = 1; i <= n; ++i) { 
        if (!h[i]) continue;
        auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
        vt.push_back(i);
      }
  
      vector<int> sequence;
      for (int i = 1; i < sz; ++i) { 
        auto& ret = pref[i];
        ret = pref[i - 1];
  
        auto& vt = i & 1 ? odd : even;
        if (!vt.size()) { ret = MAX; continue; }
        int pos = vt.front();
        vt.pop_front();
  
        ret += pos - 1 - T.que(pos - 1); 
        ret -= position.end() - upper_bound(position.begin(), position.end(), pos);
        T.upd(pos, 1);
        sequence.push_back(pos);
      }
      
      int total = totalZero;
      if (type == 1) { //calculate total
        auto& vt = (n ^ 1) & 1 ? odd : even;
        if (!vt.size()) total = MAX;
        else { 
          int pos = vt.front();
          vt.pop_front();
          total += pos - 1 - T.que(pos - 1) - Z.que(pos - 1);
          sequence.push_back(pos);
        }
      } else if (sz) { 
        auto& ret = pref[sz];
        ret = pref[sz - 1];
  
        auto& vt = sz & 1 ? odd : even;
        if (!vt.size()) ret = MAX;
        else { 
          int pos = vt.front();
          vt.pop_front();
  
          ret += pos - 1 - T.que(pos - 1); 
          ret -= position.end() - upper_bound(position.begin(), position.end(), pos);
          T.upd(pos, 1);
          sequence.push_back(pos);
        }
      }
      
      if ((int)sequence.size() == sz) {       
        if (type == 1) answer = min(answer, pref[sz - 1] + total);
        else answer = min(answer, pref[sz] + total);
  
        for (int i = (type == 1 ? sz - 2 : sz - 1); i >= 1; i -= 2) { 
          if (!(cntZero & 1)) swap(sequence[i - 1], sequence[i]);
  
          T.upd(sequence[i - 1], -1);
          T.upd(sequence[i], -1);
  
          total += sequence[i - 1] - 1 - T.que(sequence[i - 1] - 1) - Z.que(sequence[i - 1] - 1);
          T.upd(sequence[i - 1], 1);
          
          total += sequence[i] - 1 - T.que(sequence[i] - 1) - Z.que(sequence[i] - 1);
          T.upd(sequence[i], 1);
  
          T.upd(sequence[i - 1], -1);
          T.upd(sequence[i], -1);
          
          answer = min(answer, pref[i - 1] + total);
        }
      }
    }
  
    cout << (answer == MAX ? -1 : answer) << "\n";
  }
}

namespace sub5 { 
  static const int SZ = 2000 + 10;
  int bit[SZ];
  void upd(int i, int x) { 
    for (; i <= n; i += i & -i) bit[i] += x;
  } 
  int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += bit[i];
    return ret;
  }

  long long f[SZ][SZ];
  void solve() { 
    vector<int> vt(n); iota(vt.begin(), vt.end(), 1);
    sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
      return abs(h[a]) > abs(h[b]);
    });
    for (int i = 1; i <= n; ++i) upd(i, 1);

    memset(f, 14, sizeof f);
    f[0][n + 1] = 0;
    for (int i = 1; i <= n; ++i) { 
      int pos = vt[i - 1];
      upd(pos, -1);

      { // go left
        int cnt = que(pos);
        for (int l = 1; l <= i; ++l) { 
          if (((abs(pos - l) ^ (h[pos] < 0)) & 1) || !h[pos]) { 
            int r = n - i + 1 + l;
            auto& ret = f[l][r];
            ret = min(ret, f[l - 1][r] + cnt);
          }
        }
        
      }

      { // go right
        int cnt = que(n) - que(pos);
        for (int r = n; r >= n - i + 1; --r) { 
          if (((abs(pos - r) ^ (h[pos] > 0)) & 1) || !h[pos]) { 
            int l = i - (n - r + 1);
            auto& ret = f[l][r];
            ret = min(ret, f[l][r + 1] + cnt);
          }
        }
      }
    }

    long long answer = MAX;
    for (int i = 0; i <= n; ++i) answer = min(answer, f[i][i + 1]);

    cout << (answer == MAX ? -1 : answer) << "\n";
  }
}

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

  if (all_of(h + 1, h + n + 1, [](const auto& a) { return abs(a) <= 1; })) { 
    sub4::solve();
    return 0;
  };
  
  sub5::solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3