Submission #890061

#	Time	Username	Problem	Language	Result	Execution time	Memory
890061		Zero_OP	Matching (CEOI11_mat)	C++14	100 / 100	555 ms	40636 KiB

mat

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 1e6 + 5;

int n, m, a[N], b[N], pi[N], target[N], bit[N];
vector<int> ans;

void update(int id, int lim, int x){
  for(; id <= lim; id += id & (-id)){
    bit[id] += x;
  }
}

int query(int id){
  int s = 0;
  for(; id > 0; id -= id & (-id)){
    s += bit[id];
  }
  return s;
}

void computePattern(){
  for(int i = 1; i <= n; ++i){
    target[i] = query(a[i]) + 1;
    update(a[i], n, 1);
  }
  memset(bit, 0, sizeof(bit));
  pi[0] = -1;
  pi[1] = 0;

  for(int i = 2; i <= n; ++i){
    int cur = query(a[i]) + 1, j = pi[i - 1];
    while(j != -1 and target[j + 1] != cur){
      int prv = pi[j];
      for(int del = i - j; del <= i - prv - 1; ++del){
        update(a[del], n, -1);
        if(a[del] < a[i]) --cur;
      }
      j = pi[j];
    }
    pi[i] = j + 1;
    update(a[i], n, 1);
  }
}

void computeText(){
  memset(bit, 0, sizeof(bit));
  int j = -1;
  for(int i = 1; i <= m; ++i){
    int cur = query(b[i]) + 1;
    while(j == n or target[j + 1] != cur){
      int prv = pi[j];
      for(int del = i - j; del <= i - prv - 1; ++del){
        update(b[del], m, -1);
        if(b[del] < b[i]) --cur;
      }
      j = pi[j];
    }
    ++j;
    update(b[i], m, 1);
    if(j == n) ans.push_back(i - n + 1);
  }
}

void Zero_OP(){
  cin >> n >> m;
  for(int i = 1; i <= n; ++i){
    int x; cin >> x;
    a[x] = i;
  }

  vector<int> val;
  for(int i = 1; i <= m; ++i){
    cin >> b[i];
    val.push_back(b[i]);
  }

  sort(range(val));

  for(int i = 1; i <= m; ++i){
    b[i] = lower_bound(range(val), b[i]) - val.begin() + 1;
  }

  computePattern();
  computeText();

  cout << ans.size() << '\n';
  for(int i = 0; i < ans.size(); ++i){
    cout << ans[i] << ' ';
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #define task "antuvu"
  if(fopen(task".inp", "r")){
    freopen(task".inp", "r", stdin);
   // freopen(task".out", "w", stdout);
  }

  Zero_OP();

  return 0;
}

Compilation message (stderr)

mat.cpp: In function 'void Zero_OP()':
mat.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int i = 0; i < ans.size(); ++i){
      |                  ~~^~~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:118:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10