Submission #171984

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171984	2019-12-30T18:04:50 Z	AlexPop28	Matching (CEOI11_mat)	C++11	100 / 100	993 ms	38780 KB

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int INF = (int)2e9;

template<class T, class F = function<T(const T&, const T&)>>
struct Fenwick {
  int n;
  T def;
  F f;
  vector<T> tree;
  Fenwick(int n_, T def_, F f_) : n(n_), def(def_), f(f_), tree(n + 1, def) {}
  inline int lsb(int x) {
    return x & -x;
  }
  void Update(int pos, T val) {
    for (++pos; pos <= n; pos += lsb(pos)) {
      tree[pos] = f(tree[pos], val);  
    }
  }
  T Query(int pos) {
    T ret = def;
    for (++pos; pos; pos -= lsb(pos)) {
      ret = f(ret, tree[pos]);
    }
    return ret;
  }
};

void GetSmallBig(const vector<int> &p, vector<int> &small, vector<int> &big) {
  int n = p.size();
  Fenwick<pair<int, int>> mn(n, {-1, -1}, [](pair<int, int> a, pair<int, int> b) {
    return max(a, b);
  });
  Fenwick<pair<int, int>> mx(n, {INF, -1}, [](pair<int, int> a, pair<int, int> b) {
    return min(a, b);
  });
  for (int i = 0; i < n; ++i) {
    small[i] = mn.Query(p[i]).second;
    big[i] = mx.Query(n - p[i] - 1).second;
    mn.Update(p[i], make_pair(p[i], i));
    mx.Update(n - p[i] - 1, make_pair(p[i], i));
  }
}

// ffs set ul asta consuma minim 32 bytes / int ?!?!
// void GetSmallBig(const vector<int> &p, vector<int> &small, vector<int> &big) {
//   auto Comp = [&](int a, int b) {
//     return p[a] < p[b];
//   };
//   set<int, decltype(Comp)> vals(Comp);
//   vals.emplace(0);
//   for (int i = 1; i < (int)p.size(); ++i) {
//     auto it = vals.emplace(i).first;
//     if (it != vals.begin()) small[i] = *prev(it);
//     if (next(it) != vals.end()) big[i] = *next(it);
//   }
// }

bool Match(int k, int i, const vector<int> &p,
  const vector<int> &small, const vector<int> &big) {
  
  bool ret = true;
  ret &= big[k] == -1 || p[i] < p[i - k + big[k]];
  ret &= small[k] == -1 || p[i] > p[i - k + small[k]];
  return ret;
}

void GetPi(const vector<int> &p, vector<int> &pi,
  const vector<int> &small, const vector<int> &big) {

  pi[0] = 0;
  int k = 0;
  for (int i = 1; i < (int)p.size(); ++i) {
    while (k != 0 && !Match(k, i, p, small, big)) k = pi[k - 1];
    if (Match(k, i, p, small, big)) ++k;
    pi[i] = k;
  }
}

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

  int n, m; cin >> n >> m;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    int s; cin >> s; --s;
    p[s] = i;
  }

  vector<int> small(n, -1), big(n, -1), pi(n);
  GetSmallBig(p, small, big);
  GetPi(p, pi, small, big);

  vector<int> text(m);
  for (int i = 0; i < m; ++i) {
    cin >> text[i];
  }

  vector<int> ans;
  int k = 0;
  for (int i = 0; i < m; ++i) {
    while (k != 0 && !Match(k, i, text, small, big)) k = pi[k - 1];
    if (Match(k, i, text, small, big)) ++k;
    if (k == n) {
      ans.emplace_back(i - n + 1);
      k = pi[k - 1];
    }
  }

  cout << ans.size() << endl;
  for (int &x : ans) {
    cout << 1 + x << ' ';
  }
  cout << endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	508 KB	Output is correct
2	Correct	6 ms	632 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	504 KB	Output is correct
2	Correct	6 ms	632 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	1736 KB	Output is correct
2	Correct	26 ms	2552 KB	Output is correct
3	Correct	58 ms	4128 KB	Output is correct
4	Correct	58 ms	4072 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	2300 KB	Output is correct
2	Correct	36 ms	3248 KB	Output is correct
3	Correct	43 ms	3740 KB	Output is correct
4	Correct	43 ms	4592 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	2428 KB	Output is correct
2	Correct	45 ms	3408 KB	Output is correct
3	Correct	44 ms	3432 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	271 ms	8896 KB	Output is correct
2	Correct	993 ms	38648 KB	Output is correct
3	Correct	133 ms	11540 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	310 ms	10304 KB	Output is correct
2	Correct	133 ms	10948 KB	Output is correct
3	Correct	927 ms	36832 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	162 ms	6348 KB	Output is correct
2	Correct	217 ms	22116 KB	Output is correct
3	Correct	188 ms	12688 KB	Output is correct
4	Correct	662 ms	38780 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	189 ms	7776 KB	Output is correct
2	Correct	191 ms	13744 KB	Output is correct
3	Correct	109 ms	8164 KB	Output is correct
4	Correct	672 ms	34880 KB	Output is correct

Submission #171984

Compilation message