# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127104 | 2019-07-08T22:26:12 Z | eriksuenderhauf | Matching (CEOI11_mat) | C++11 | 510 ms | 48848 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e6 + 5; const double eps = 1e-9; int nxl[MAXN], nxr[MAXN], b[MAXN]; int lp[MAXN], rp[MAXN], f[MAXN]; int s[MAXN], h[MAXN], a[MAXN]; int n, m; vi ans; int f1(int x) { if (x < 0) return x; if (nxl[x] == x) return x; return nxl[x] = f1(nxl[x]); } int f2(int x) { if (x >= n) return x; if (nxr[x] == x) return x; return nxr[x] = f2(nxr[x]); } bool g1(int x, int p) { return a[x - lp[p]] <= a[x] && a[x] <= a[x - rp[p]]; } bool g2(int x, int p) { return h[x - lp[p]] <= h[x] && h[x] <= h[x - rp[p]]; } int main() { ni(n), ni(m); for (int i = 0; i < n; i++) { ni(s[i]); s[i]--; a[s[i]] = i; nxl[i] = nxr[i] = i; } for (int i = n - 1; i >= 0; i--) { nxl[a[i]] = f1(a[i] - 1); nxr[a[i]] = f2(a[i] + 1); if (nxr[a[i]] < n) rp[i] = i - s[nxr[a[i]]]; if (nxl[a[i]] >= 0) lp[i] = i - s[nxl[a[i]]]; } int p = 0; for (int i = 1; i < n; i++) { while (p > 0 && !g1(i, p)) p = f[p]; if (g1(i, p)) p++; f[i + 1] = p; } p = 0; for (int i = 0; i < m; i++) { ni(h[i]); while (p > 0 && !g2(i, p)) p = f[p]; if (g2(i, p)) p++; if (p == n) ans.pb(i - n + 2), p = f[p]; } pri(ans.size()); for (int i: ans) printf("%d ", i); enl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 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 | 380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 380 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 5 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 732 KB | Output is correct |
2 | Correct | 6 ms | 760 KB | Output is correct |
3 | Correct | 3 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 3832 KB | Output is correct |
2 | Correct | 29 ms | 2552 KB | Output is correct |
3 | Correct | 54 ms | 4744 KB | Output is correct |
4 | Correct | 54 ms | 4788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 4728 KB | Output is correct |
2 | Correct | 46 ms | 3240 KB | Output is correct |
3 | Correct | 46 ms | 4216 KB | Output is correct |
4 | Correct | 48 ms | 4588 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 4832 KB | Output is correct |
2 | Correct | 40 ms | 4236 KB | Output is correct |
3 | Correct | 42 ms | 3832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 217 ms | 21620 KB | Output is correct |
2 | Correct | 510 ms | 48024 KB | Output is correct |
3 | Correct | 152 ms | 11896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 219 ms | 23160 KB | Output is correct |
2 | Correct | 167 ms | 11008 KB | Output is correct |
3 | Correct | 457 ms | 43552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 174 ms | 14704 KB | Output is correct |
2 | Correct | 235 ms | 21960 KB | Output is correct |
3 | Correct | 202 ms | 16220 KB | Output is correct |
4 | Correct | 316 ms | 48848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 179 ms | 16696 KB | Output is correct |
2 | Correct | 203 ms | 16444 KB | Output is correct |
3 | Correct | 91 ms | 9720 KB | Output is correct |
4 | Correct | 350 ms | 45048 KB | Output is correct |