Submission #930088

#TimeUsernameProblemLanguageResultExecution timeMemory
930088Mohammadamin__ShLottery (CEOI18_lot)C++17
80 / 100
1010 ms8252 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][101]; vector<int> query , allq; int 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'; } }

Compilation message (stderr)

lot.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("O2")
      |
#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...