Submission #721162

#	Time	Username	Problem	Language	Result	Execution time	Memory
721162		lto5	Matching (CEOI11_mat)	C++14	63 / 100	403 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 a[N];
int b[N];
int64_t p[N];
int64_t sp[N];

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

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

  SegTree *lf, *rt;
  int l, r;
  Node val;
  int lazy;

  SegTree(int lo = 1, int hi = 0) {
    lf = rt = NULL;
    l = lo, r = hi;
    val = Node(0, 0);
    lazy = 0;
  }

  void expand() {
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    if (lf == NULL) {
      lf = new SegTree(l, mid);
    }
    if (rt == NULL) {
      rt = new SegTree(mid + 1, r);
    }
  }

  void push_lazy() {
    if (l == r) {
      return;
    }
    expand();
    lf->lazy += lazy;
    if (lf->val.len)
      sub(lf->val.value, sp[lf->val.len - 1] * lazy % MOD);
    rt->lazy += lazy;
    if (rt->val.len)
      sub(rt->val.value, sp[rt->val.len - 1] * lazy % MOD);
    lazy = 0;
  }

  void add(int i, int v) {
    if (i < l || r < i) {
      return;
    }
    if (l == r) {
      val = Node(1, v);
      return;
    }
    push_lazy();
    lf->add(i, v);
    rt->add(i, v);
    val = lf->val + rt->val;
  }

  void del(int i) {
    if (i < l || r < i) {
      return;
    }
    if (l == r) {
      val = Node(0, 0);
      return;
    }
    push_lazy();
    lf->del(i);
    rt->del(i);
    val = lf->val + rt->val;
  }

  void dec(int u, int v) {
    if (v < l || r < u) {
      return;
    }
    if (u <= l && r <= v) {
      lazy++;
      if (val.len)
        sub(val.value, sp[val.len - 1]);
      return;
    }
    push_lazy();
    lf->dec(u, v);
    rt->dec(u, v);
    val = lf->val + rt->val;
  }

  Node get(int u, int v) {
    if (v < l || r < u) {
      return Node();
    }
    if (u <= l && r <= v) {
      return val;
    }
    push_lazy();
    return lf->get(u, v) + rt->get(u, v);
  }
};

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;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }
  int64_t h = 0;
  p[0] = 1;
  sp[0] = 1;
  for (int i = 1; i <= m; i++) {
    p[i] = p[i - 1] * BASE % MOD;
    sp[i] = (sp[i - 1] + p[i]) % MOD;
  }
  for (int i = 1; i <= n; i++) {
    h = (h * BASE + a[i]) % MOD;
  }
  // {
  //   vector<int> v = {1, 2, 4, 5};
  //   int64_t vl = 0;
  //   for (int i : v) {
  //     vl = (vl * BASE + i) % MOD;
  //   }
  //   cerr << vl << endl;
  // }
  Compressor<int> cps(b, m);
  // for (int x : cps.val) {
  //   cerr << x << ", ";
  // }
  // cerr << endl;
  // assert(is_sorted(cps.val.begin(),cps.val.end()));
  SegTree* root = new SegTree(1, m);
  for (int i = 1; i <= n; i++) {
    b[i] = cps.idx(b[i]);
    root->add(b[i], i);
    // cerr << b[i] << ", ";
  }
  // cerr << endl;
  vector<int> ans;
  // cerr << root->val.value << " " << h << endl;
  if (root->val.value == h) {
    ans.push_back(1);
  }
  for (int i = n + 1; i <= m; i++) {
    // cerr << i << " ";
    b[i] = cps.idx(b[i]);
    root->del(b[i - n]);
    // if (i == 6) {
    //   for (int j = 1; j <= 5; j++) {
    //     cerr << root->get(b[j], b[j]).value << " \n"[j == 5];
    //   }
    // }
    // cerr << root->val.value << " ";
    root->dec(1, m);
    // if (i == 6) {
    //   for (int j = 1; j <= 5; j++) {
    //     cerr << root->get(b[j], b[j]).value << " \n"[j == 5];
    //   }
    // }
    root->add(b[i], n);
    // cerr << root->val.value << endl;
    if (root->val.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:161:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10