제출 #936928

#제출 시각아이디문제언어결과실행 시간메모리
936928_callmelucianMatching (CEOI11_mat)C++14
63 / 100
856 ms65536 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) struct pBIT { vector<vector<pii>> tr; pBIT (int sz) : tr(sz + 1, vector<pii>(1, make_pair(-1, 0))) {} int get (int k, int ver) { auto it = upper_bound(all(tr[k]), make_pair(ver, INT_MAX)); return prev(it)->second; } int p (int k) { return k & -k; } void update (int k, int val, int ver) { for (; k < tr.size(); k += p(k)) { int cur = tr[k].back().second + val; tr[k].push_back(make_pair(ver, cur)); } } int query (int k, int ver, int ans = 0) { for (; k; k -= p(k)) ans += get(k, ver); return ans; } }; vector<int> pFunc (vector<int> &vec, int sz) { int n = vec.size(); vector<int> pi(n); pBIT tree(sz); for (int i = 0; i < n; i++) if (vec[i] < INT_MAX) tree.update(vec[i], 1, i); function<int(int,int)> countSmall = [&] (int l, int r) { return tree.query(vec[r], r) - tree.query(vec[r], l - 1); }; function<bool(int,int)> same = [&] (int i, int j) { // [0..i-1] + i == [j-i..j-1] + j if (vec[i] == INT_MAX || vec[j] == INT_MAX) return false; return countSmall(0, i) == countSmall(j - i, j); }; for (int i = 1; i < n; i++) { int j = pi[i - 1]; while (j && !same(j, i)) j = pi[j - 1]; if (same(j, i)) pi[i] = j + 1; } return pi; } map<int,int> mp; void compress() { int mark = 0; for (pii it : mp) mp[it.first] = ++mark; } int main() { //freopen("oke.inp", "r", stdin); //freopen("oke.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<int> s(n), h(m); for (int i = 1; i <= n; i++) { int p; cin >> p; s[p - 1] = i; } for (int i = 0; i < m; i++) { cin >> h[i]; mp[h[i]] = 0; } compress(); vector<int> vec = s; vec.push_back(INT_MAX); for (int u : h) vec.push_back(mp[u]); vector<int> pi = pFunc(vec, max(n, m)), ans; for (int i = 0; i < pi.size(); i++) if (pi[i] == n) ans.push_back(i - 2 * n + 1); cout << ans.size() << "\n"; for (int u : ans) cout << u << " "; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp: In member function 'void pBIT::update(int, int, int)':
mat.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; k < tr.size(); k += p(k)) {
      |                ~~^~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < pi.size(); i++)
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...