Submission #792016

#TimeUsernameProblemLanguageResultExecution timeMemory
792016DanetLottery (CEOI18_lot)C++14
100 / 100
370 ms12332 KiB
#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 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...