Submission #721171

#	Time	Username	Problem	Language	Result	Execution time	Memory
721171		lto5	Matching (CEOI11_mat)	C++14	100 / 100	1674 ms	65536 KiB

mat

#include <bits/stdc++.h>

using namespace std;

const int BASE = (int)1e6 + 3;
const int MOD = 1e9 + 7;
const int N = 1e6 + 5;

int n, m;
int b[N];
int p[N];
int sp[N];

struct Node {
  int len;
  int value;
  Node(int l = 0, int a = 0) {
    len = l;
    value = a;
  }
  Node operator+(const Node& rhs) const {
    return Node(len + rhs.len, (1ll * value * p[rhs.len] % MOD + rhs.value) % MOD);
  }
};

Node st[N << 2];
int lazy[N << 2];

void sub(int& a, int b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}

void push(int id) {
  if (!lazy[id]) {
    return;
  }
  for (int i = (id << 1); i <= (id << 1 | 1); i++) {
    if (st[i].len)
      sub(st[i].value, 1ll * lazy[id] * sp[st[i].len - 1] % MOD);
    lazy[i] += lazy[id];
  }
  lazy[id] = 0;
}

void add(int id, int l, int r, int i, int v) {
  if (i < l || r < i) {
    return;
  }
  if (l == r) {
    st[id] = Node(1, v);
    return;
  }
  push(id);
  int mid = (l + r) >> 1;
  add(id << 1, l, mid, i, v);
  add(id << 1 | 1, mid + 1, r, i, v);
  st[id] = st[id << 1] + st[id << 1 | 1];
}

void del(int id, int l, int r, int i) {
  if (i < l || r < i) {
    return;
  }
  if (l == r) {
    st[id] = Node(0, 0);
    return;
  }
  push(id);
  int mid = (l + r) >> 1;
  del(id << 1, l, mid, i);
  del(id << 1 | 1, mid + 1, r, i);
  st[id] = st[id << 1] + st[id << 1 | 1];
}

void dec(int id, int l, int r, int u, int v) {
  if (v < l || r < u) {
    return;
  }
  if (u <= l && r <= v) {
    lazy[id]++;
    if (st[id].len) {
      sub(st[id].value, sp[st[id].len - 1]);
    }
    return;
  }
  push(id);
  int mid = (l + r) >> 1;
  dec(id << 1, l, mid, u, v);
  dec(id << 1 | 1, mid + 1, r, u, v);
  st[id] = st[id << 1] + st[id << 1 | 1];
}

template <class T>
struct Compressor {
#define all(x) (x).begin(), (x).end()
  vector<T> val;
  void add(T x) {
    val.push_back(x);
  }
  void init() {
    sort(all(val));
    val.resize(unique(all(val)) - val.begin());
  }
  Compressor(vector<T> v) {
    val = v;
    init();
  }
  Compressor(T* a, int n, int one = 1) {
    val = vector<T>(a + one, a + n + one);
    init();
  }
  int idx(T x) {
    return lower_bound(all(val), x) - val.begin() + 1;
  }
#undef all
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> m;
  int h = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    h = (1ll * h * BASE % MOD + x) % MOD;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }
  p[0] = 1;
  sp[0] = 1;
  for (int i = 1; i <= m; i++) {
    p[i] = 1ll * p[i - 1] * BASE % MOD;
    sp[i] = (sp[i - 1] + p[i]) % MOD;
  }
  Compressor<int> cps(b, m);
  for (int i = 1; i <= n; i++) {
    b[i] = cps.idx(b[i]);
    add(1, 1, m, b[i], i);
  }
  vector<int> ans;
  if (st[1].value == h) {
    ans.push_back(1);
  }
  for (int i = n + 1; i <= m; i++) {
    b[i] = cps.idx(b[i]);
    del(1, 1, m, b[i - n]);
    dec(1, 1, m, 1, m);
    add(1, 1, m, b[i], n);
    if (st[1].value == h) {
      ans.push_back(i - n + 1);
    }
  }
  cout << ans.size() << "\n";
  for (int i : ans) {
    cout << i << " ";
  }
  return 0;
}

/**
 * b[]          = [b_1, b_2, ..., b_n]
 * id[]         = [1, 2, ..., n]
 * sorted(id) == a --> is a starting point
 */

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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