Submission #924076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924076	2024-02-08T11:33:20 Z	dubabuba	Matching (CEOI11_mat)	C++14	100 / 100	683 ms	65536 KB

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

#define MAX 1000000
#define INFTY 100000000

/* p1 is the original pattern from the problem statement, while
 * p is given from left to right, like the text t. */
int n, m;
int p1[MAX + 1], p[MAX + 1], t[MAX + 1];

void read()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> p1[i];
  }
  for (int i = 1; i <= n; i++)
    p[p1[i]] = i;
  for (int i = 1; i <= m; i++)
    cin >> t[i];
}


/* Segment trees, efficient implementation. */
pair<int, int> min_tree[1 << 21], max_tree[1 << 21];
int size;

void init_trees()
{
  size = 1;
  while (size <= n)
    size *= 2;
  for (int i = 0; i <= 2 * size - 1; i++)
  {
    min_tree[i] = make_pair(INFTY, -1);
    max_tree[i] = make_pair(-1, -1);
  }
}

int max_query(int v)
{
  int ind = size + v;
  pair<int, int> res = make_pair(-1, -1);
  while (ind != 1)
  {
    if (ind % 2 == 1 && max_tree[ind - 1].first > res.first)
      res = max_tree[ind - 1];
    ind /= 2;
  }
  return res.second;
}

int min_query(int v)
{
  int ind = size + v;
  pair<int, int> res = make_pair(INFTY, -1);
  while (ind != 1)
  {
    if (ind % 2 == 0 && min_tree[ind + 1].first < res.first)
      res = min_tree[ind + 1];
    ind /= 2;
  }
  return res.second;
}

void min_insert(pair<int, int> p)
{
  int ind = size + p.first;
  min_tree[ind] = p;
  while (ind != 1)
  {
    ind /= 2;
    if (p.first < min_tree[ind].first)
      min_tree[ind] = p;
  }
}

void max_insert(pair<int, int> p)
{
  int ind = size + p.first;
  max_tree[ind] = p;
  while (ind != 1)
  {
    ind /= 2;
    if (p.first > max_tree[ind].first)
      max_tree[ind] = p;
  }
}


int g[MAX + 1], h[MAX + 1];

/* Computes the g and h functions, as defined in the solution description,
 * using a segment tree. */
void compute_gh()
{
  init_trees();
  for (int i = 1; i <= n; i++)
  {
    g[i] = max_query(p[i]);
    h[i] = min_query(p[i]);
    min_insert(make_pair(p[i], i));
    max_insert(make_pair(p[i], i));
  }
}


int f[MAX + 1];

inline bool matches(int pos, int pos2)
{
  if (g[pos] != -1 && p[pos2] <= p[pos2 - (pos - g[pos])])
    return false;
  if (h[pos] != -1 && p[pos2] >= p[pos2 - (pos - h[pos])])
    return false;
  return true;
}

inline bool matches_t(int pos, int pos2)
{
  if (g[pos] != -1 && t[pos2] <= t[pos2 - (pos - g[pos])])
    return false;
  if (h[pos] != -1 && t[pos2] >= t[pos2 - (pos - h[pos])])
    return false;
  return true;
}

/* Computes the failure function of the pattern. */
void compute_f()
{
  f[0] = f[1] = 0;
  int last = 0;
  for (int i = 2; i <= n; i++)
  {
    f[i] = last;
    while (last && !matches(last + 1, i))
      last = f[last];
    if (matches(last + 1, i))
      last++;
    f[i] = last;
  }
}


vector<int> result;

void matching()
{
  int last = 0;
  for (int i = 1; i <= m; i++)
  {
    while (last && !matches_t(last + 1, i))
      last = f[last];
    if (matches_t(last + 1, i))
      last++;
    if (last == n)
    {
      result.push_back(i - n + 1);
      last = f[last];
    }
  }
}

void write()
{
  cout << result.size() << endl;
  for (int i = 0; i < (int)result.size(); i++)
  {
    cout << result[i];
    if (i < (int)result.size() - 1)
      cout << " ";
  }
  cout << endl;
}

int main()
{
  ios_base::sync_with_stdio(0);
  read();
  compute_gh();
  compute_f();
  matching();
  write();
  return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	2 ms	14684 KB	Output is correct
4	Correct	2 ms	14684 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	14940 KB	Output is correct
2	Correct	5 ms	14940 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	14940 KB	Output is correct
2	Correct	4 ms	14964 KB	Output is correct
3	Correct	2 ms	14684 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	20532 KB	Output is correct
2	Correct	17 ms	18144 KB	Output is correct
3	Correct	38 ms	25232 KB	Output is correct
4	Correct	37 ms	25176 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	25168 KB	Output is correct
2	Correct	22 ms	18748 KB	Output is correct
3	Correct	26 ms	19140 KB	Output is correct
4	Correct	27 ms	20176 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	25300 KB	Output is correct
2	Correct	28 ms	22612 KB	Output is correct
3	Correct	28 ms	18772 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	41944 KB	Output is correct
2	Correct	683 ms	65536 KB	Output is correct
3	Correct	78 ms	24404 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	53824 KB	Output is correct
2	Correct	77 ms	23368 KB	Output is correct
3	Correct	648 ms	65536 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	31952 KB	Output is correct
2	Correct	126 ms	34488 KB	Output is correct
3	Correct	114 ms	32836 KB	Output is correct
4	Correct	366 ms	65536 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	34504 KB	Output is correct
2	Correct	116 ms	33364 KB	Output is correct
3	Correct	65 ms	29228 KB	Output is correct
4	Correct	383 ms	65536 KB	Output is correct

Submission #924076

Compilation message