This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define Tof_Io ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define int long long int
#define F first
#define S second
#define tagh2(j) j>>1
#define zarb2(j) j<<1
const int MX=2e4+23,mod=1e9+7,mod1 = 1e9+7;
const long long INF = 1ll << 60;
const int N = 1e4 + 5;
const int Q = 100 + 5;
int inv[MX], fac[MX];
int pwe(int a, int b, int md = mod){int res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
void modplus(int &j,int y){(j+=y)>=mod && (j-=mod);}
bool isprime(int n){bool fl = 1;for (int i = 2; i <= sqrt(n)+1; i++){if(n%i==0){fl = 0;break;}}return fl;}
void printt(bool fl){if(fl==1){cout << "YES";return;}cout << "NO";}
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
int MOD(int a, int b=mod1){ int res = a + b; return (res >= mod? res - mod : res); }
int LCM(int a, int b) {return a/GCD(a,b)*b;}
int lis(vector<int>& v){if (v.size() == 0) {return 0;} vector<int> tail(v.size(), 0); int szgth = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + szgth; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + szgth){tail[szgth++] = v[i];}else{*it = v[i];}} return szgth;}
int yay(int n){return (1ull << n);}
int C(int n,int r){return fac[n] * inv[r] % mod * inv[n-r] % mod;}
void build(){fac[0] = 1; inv[0] = pwe(fac[0],mod-2);for(int i = 1 ; i< MX ; i ++) {fac[i] = (fac[i-1] * i)%mod;inv[i] = pwe(fac[i],mod-2);}}
int dp[N], ans[Q][N], n, q, a[N], K[N], l, ps[N];
void add(const int k)
{
memset(ps, 0, sizeof ps);
for (int i = 0; i <= n - l; i++) ps[dp[i]]++;
for (int i = 1; i <= l; i++) ps[i] += ps[i - 1];
for (int i = 0; i < q; i++) ans[i][k] = ps[K[i]];
}
int32_t main()
{
cin >> n >> l;
for (int i = 0; i < n; i++) cin >> a[i];
cin >> q;
for (int i = 0; i < q; i++) cin >> K[i];
for (int i = 0; i <= n - l; i++) for (int j = 0; j < l; j++) dp[i] += a[j] != a[j + i];
add(0);
for (int i = 1; i <= n - l; i++)
{
for (int j = n - l; j; j--) dp[j] = dp[j - 1] + (a[i + l - 1] != a[j + l - 1]) - (a[i - 1] != a[j - 1]);
dp[0] = 0;
for (int j = 0; j < l; j++) dp[0] += a[j] != a[j + i];
add(i);
}
for (int i = 0; i < q; i++)
{
for (int j = 0; j <= n - l; j++)
{
cout << ans[i][j] - 1 << ' ';
}
cout << endl;
}
return 0;
}
Compilation message (stderr)
lot.cpp: In function 'long long int lis(std::vector<long long int>&)':
lot.cpp:24:136: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | int lis(vector<int>& v){if (v.size() == 0) {return 0;} vector<int> tail(v.size(), 0); int szgth = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + szgth; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + szgth){tail[szgth++] = v[i];}else{*it = v[i];}} return szgth;}
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |