Submission #551775

#	Time	Username	Problem	Language	Result	Execution time	Memory
551775		cadmiumsky	Rope (JOI17_rope)	C++14	100 / 100	1300 ms	92324 KiB

rope

#include <bits/stdc++.h>

using namespace std;
const int nmax = 1e6 + 5, mmax = 1e6 + 5;
int N, m, rez[mmax];
vector<int> g[mmax];

namespace MO {
  int freq[mmax], ffreq[nmax];
  int ptr = 0;
  void init() {memset(freq, 0, sizeof(freq)), memset(ffreq, 0, sizeof(ffreq)), ptr = 0;}
  void ignore(int x) {
    ffreq[freq[x]]--;
    while(ptr > 0 && ffreq[ptr] == 0)
      ptr--;
  }
  void reinsert(int x) {
    ffreq[freq[x]]++;
    ptr = max(freq[x], ptr);
  }
  void add(int x, int aggr) {
    ffreq[freq[x]]--;
    freq[x] += aggr;
    ffreq[freq[x]]++;
    while(ffreq[ptr + 1] > 0)
      ptr++;
    while(ptr > 0 && ffreq[ptr] == 0)
      ptr--;
  }
}

static void solve(vector<int> v) {
  int n = v.size();
  assert(n % 2 == 0);
  for(int i = 0; i < m; i++) g[i].clear();
  for(int i = 0; i < n; i += 2) {
    if(v[i] != v[i + 1])
      g[v[i]].push_back(v[i + 1]),
      g[v[i + 1]].push_back(v[i]);
    MO::add(v[i], 1);
    MO::add(v[i + 1], 1);
  }
  for(int i = 0, collat; i < m; i++) {
    MO::ignore(i);
    collat = g[i].size();
    for(auto x : g[i])
      MO::add(x, -1);
    rez[i] = min(rez[i], collat + (N - (MO::freq[i] + collat)) - MO::ptr);
    for(auto x : g[i])
      MO::add(x, 1);
    MO::reinsert(i);
  }
}

int main() {
  int n;
  cin >> n >> m;
  N = n;
  vector<int> v(n), temp;
  for(auto &x : v)
    cin >> x, --x;
  for(int i = 0; i < m; i++)
    rez[i] = N * 2;
  MO::init();
  temp = v;
  if(n % 2 == 1)
    MO::add(v.back(), 1), v.pop_back();
  solve(v);
  v = temp;
  MO::init();
  MO::add(v[0], 1);
  if(n % 2 == 0)  
    MO::add(v.back(), 1), v.pop_back();
  reverse(v.begin(), v.end()); v.pop_back();
  reverse(v.begin(), v.end()); 
  solve(v);
  for(int i = 0; i < m; i++)
    cout << rez[i] << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20