oj.uz

Submission #721171

# Submission time Handle Problem Language Result Execution time Memory
721171 2023-04-10T12:39:36 Z lto5 Matching (CEOI11_mat) C++14
100 / 100
 1674 ms 65536 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 16 ms 31560 KB Output is correct
3 Correct 15 ms 31588 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31700 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32208 KB Output is correct
2 Correct 29 ms 32176 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 32172 KB Output is correct
2 Correct 30 ms 32172 KB Output is correct
3 Correct 17 ms 31700 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 36428 KB Output is correct
2 Correct 191 ms 36728 KB Output is correct
3 Correct 263 ms 36804 KB Output is correct
4 Correct 256 ms 36760 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 37196 KB Output is correct
2 Correct 299 ms 36736 KB Output is correct
3 Correct 219 ms 37108 KB Output is correct
4 Correct 179 ms 38940 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 37184 KB Output is correct
2 Correct 183 ms 36792 KB Output is correct
3 Correct 212 ms 36780 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 65536 KB Output is correct
2 Correct 1071 ms 63784 KB Output is correct
3 Correct 1131 ms 59616 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 64992 KB Output is correct
2 Correct 1674 ms 62228 KB Output is correct
3 Correct 1067 ms 65536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 64536 KB Output is correct
2 Correct 931 ms 65536 KB Output is correct
3 Correct 1315 ms 65068 KB Output is correct
4 Correct 563 ms 61776 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 64852 KB Output is correct
2 Correct 1262 ms 65536 KB Output is correct
3 Correct 514 ms 47772 KB Output is correct
4 Correct 689 ms 64472 KB Output is correct