Submission #930092

#TimeUsernameProblemLanguageResultExecution timeMemory
930092Mohammadamin__ShLottery (CEOI18_lot)C++17
100 / 100
1063 ms12504 KiB
//In His Name #include <bits/stdc++.h> //#pragma GCC optimization("O2") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx2") using namespace std; #define ll long long #define int ll typedef pair<int, int> pii; #define F first #define S second #define pb push_back #define bug(x) cout << "Ah shit , here we go again : " << x <<endl #define all(x) x.begin() , x.end() const int maxn = 1e4 + 10, MOD = 1e9 + 7; const ll INF = 1e18; int n , l , a[maxn] , q , dp[maxn][105]; vector<int> query , allq; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> l; for(int i = 1 ; i <= n ; i++) cin >> a[i]; cin >> q; for(int i = 1 ; i <= q ; i++){ int x; cin >> x; query.pb(x) , allq.pb(x); } sort(all(query)); query.resize(unique(all(query)) - query.begin()); for(int i = 1 ; i <= n-l ; i++) { int w = 0; for(int k = 1 ; k <= l ; k++) if(a[i+k] == a[k]) w++; int idx = lower_bound(all(query) , l - w) - query.begin() + 1 ; dp[i+1][idx]++ , dp[1][idx]++; for(int k = 2 ; k+i <= n-l+1 ; k++){ if(a[k+l-1] == a[i+k+l-1]) w++; if(a[k-1] == a[i+k-1]) w--; idx = lower_bound(all(query) , (l - w)) - query.begin() + 1 ; dp[k][idx]++ , dp[i+k][idx]++; } } for(int i = 1 ; i <= n-l+1 ; i++) for(int j = 1 ; j <= q ; j++) dp[i][j] += dp[i][j-1]; for(int j = 0 ; j < q ; j++){ int x = allq[j]; int idx = lower_bound(all(query) , x) - query.begin() + 1 ; for(int i = 1 ; i <= n-l+1 ; i++) cout << dp[i][idx] << " "; cout << '\n'; } }
#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...