제출 #1187476

#제출 시각아이디문제언어결과실행 시간메모리
1187476od_aliMatching (CEOI11_mat)C++20
63 / 100
738 ms67780 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define He_he_boy ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define ld long double #define pb push_back #define pf push_front #define eb emplace_back #define fi first #define se second #define ull unsigned long long #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define mx_e max_element #define open freopen("fcolor.in", "r", stdin); #define close freopen("fcolor.out", "w", stdout); #define endl cout << '\n' #define run(a) for (ll w23 = 1; w23 <= a; w23++) typedef long long ll; using namespace std; const ld eps = 0.00001, Pi = 3.14159275358979323846; const ll mod = 1e9 + 7; ll mod2 = 37, tt; /// -------------------------------------------------------- ll n, m; ll a[1000010]; ll b[1000010], p[1000010]; ll T[4000010], Sz[4000010]; void up(ll x, ll l, ll r, ll j, ll v){ if(l > j or r < j) return; if(l == r){ T[x] = v; Sz[x] = (v > 0); return; } ll m = (l + r) / 2; up(x * 2, l, m, j, v); up(x * 2 + 1, m + 1, r, j, v); ll k = Sz[2 * x]; T[x] = T[x + x] + (p[k] * T[2 * x + 1]) % mod;T[x] %= mod; Sz[x] = k + Sz[2 * x + 1]; } void Ali() { cin >> n >> m; for(ll i = 1;i <= n;i ++){ cin >> a[i]; } for(ll i = 1;i <= m;i ++){ cin >> b[i]; } ll ans = 1; for(ll i = 1;i < n;i ++){ ans = (ans + p[i]) % mod; } vector<pair<ll, ll>>v; for(ll i = 1;i <= m;i ++){ v.pb({b[i], i}); } sort(all(v)); for(ll i = 0 ;i < m;i ++){ b[v[i].se] = i + 1; } ll Hs = 0; for(ll i = 1;i <= n;i ++){ Hs = (Hs + (a[i] * p[i - 1]) % mod) % mod; } vector<ll>ot; for(ll j = 1;j <= m;j ++){ up(1, 1, m, b[j], j); if(Sz[1] >= n){ if(Sz[1] > n){ up(1, 1, m, b[j - n], 0); Hs = (Hs + ans) % mod; } if(T[1] == Hs){ ot.pb(j - n + 1); } } } cout << ot.size() << '\n'; for(auto to : ot){ cout << to << ' '; } cout << '\n'; } /// -------------------------------------------------------- int main() { // open // close; // He_he_boy; ll gg = 1; tt = 0;p[0] = 1; for(ll i = 1;i <= 1e6 + 2;i ++){ p[i] = (p[i - 1] * mod2) % mod; } // cin >> gg; while (gg--) { Ali(); // cout << '\n'; } /* **PLUS ULTRA** */ return 0; }
#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...