제출 #167830

#제출 시각아이디문제언어결과실행 시간메모리
167830kostia244Lottery (CEOI18_lot)C++17
45 / 100
139 ms33144 KiB
#include<bits/stdc++.h> #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; using ll = long long; using vi = vector<int>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); short cmp[2020][2020], dp[2020][2020]; int n, l, q; vi a; const int mod = 1e9 + 9; const int base = 11000 + rng()%10000; ll pw[10100]; map<int, int> hsh; void solve2() { ll hash = 0; for(int i = 0; i < n; i++) { hash = (hash*base + a[i])%mod; if(i-l>=0) { hash = hash-(pw[l]*a[i-l])%mod; if(hash<0) hash+=mod; } if(i-l+1>=0) hsh[hash]++; } hash = 0; for(int i = 0; i < n; i++) { hash = (hash*base + a[i])%mod; if(i-l>=0) { hash = hash-(pw[l]*a[i-l])%mod; if(hash<0) hash+=mod; } if(i-l+1>=0) cout << hsh[hash]-1 << " "; } exit(0); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); pw[0] = 1; for(int i = 1; i < 10100; i++) pw[i] = (pw[i-1]*1ll*base)%mod; cin >> n >> l; a.resize(n); for(auto &i : a)cin >> i; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) dp[i][j] = a[i]!=a[j]; int cmped = 0; for(int k = 0; (1<<k) <= l; k++) { if((1<<k)&l) { for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { cmp[i][j] += dp[i+cmped][j+cmped]; } } cmped += (1<<k); } for(int i = 0; i+(1<<k) < n; i++) { for(int j = i+1; j+(1<<k) < n; j++) { dp[i][j] += dp[i+(1<<k)][j+(1<<k)]; } } } int q, z; cin >> q; int ans[10010]; while(q--) { cin >> z; if(q==0&&z==0) solve2(); memset(ans, 0, sizeof ans); for(int i = 0; i+l-1 < n; i++) { for(int j = i+1; j+l-1 < n; j++) ans[i] += cmp[i][j]<=z, ans[j]+=cmp[i][j]<=z; cout << ans[i] << ' '; } 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...