Submission #666377

#	Time	Username	Problem	Language	Result	Execution time	Memory
666377		ktkerem	Lottery (CEOI18_lot)	C++17	0 / 100	2 ms	596 KiB

lot

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
/**/
typedef int ll;
//typedef long long ll;
typedef unsigned long long ull;
typedef std::string str;
/*typedef __int128 vll;
typedef unsigned __int128 uvll;*/
#define llll std::pair<ll , ll>
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e15 + 7; 
const ll ous = 1e5 + 7;
const ll dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0,1,0,-1};
ll n , m;std::vector<ll> ar;
void solve(){
    std::cin >> n >> m;
    ar.resize(n);
    for(ll i = 0;n>i;i++){
        std::cin >> ar[i];    
    }
    ll q;std::cin >> q;
    ll ans[q+1][n - m + 1];
    memset(ans , 0 , sizeof(ans));
    std::vector<llll> que;
    que.pb({limit , limit});
    for(ll i = 0;q>i;i++){
        ll x;std::cin >> x;
        que.pb({x , i});
    }
    std::sort(all(que));
    for(ll i = 1;n - m>=i;i++){
        ll cst = 0;
        for(ll j = 0;m>j;j++){
            cst += (ar[j] != ar[i + j]);
        }
        llll y = {cst , -limit};
        ll o = std::lower_bound(all(que) , y) - que.begin();
        ans[que[o].sec][0]++;
        ans[que[o].sec][i]++;
        for(ll j = m;n>j+i;j++){
            cst -= (ar[j - m] != ar[j-m+i]);
            cst += (ar[j] != ar[j + i]);
            y = {cst , -limit};
            o = std::lower_bound(all(que) , y) - que.begin();
            ans[que[o].sec][j - m + 1]++;
            ans[que[o].sec][i + j - m + 1]++;
        }
    }
    for(ll i =1;q>i;i++){
        for(ll j =0;n-m+1>j;j++){
            ans[que[i].sec][j] += ans[que[i-1].sec][j]; 
        }
    }
    for(ll i =0;q>i;i++){
        for(ll j =0;n-m+1>j;j++){
            std::cout << ans[i][j] << " ";
        }
        std::cout << "\n";
    }
    return;/**/
}
signed main(){
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0;
}/**/

Compilation message (stderr)

lot.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
lot.cpp:21:23: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.000000000000007e+15' to '2147483647' [-Woverflow]
   21 | const ll limit = 1e15 + 7;
      |                  ~~~~~^~~
lot.cpp: In function 'int main()':
lot.cpp:75:8: warning: unused variable 'o' [-Wunused-variable]
   75 |     ll o = 1;
      |        ^

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20