Submission #1104344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104344		underwaterkillerwhale	Lottery (CEOI18_lot)	C++17	100 / 100	616 ms	6472 KiB

lot

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e4 + 7;
const int Mod = 1e6 + 3;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 200;

int n, L, Q;
int a[N];
short f[2][N], g[2][N], pre[N];
short Ans[107][N], qr[107];

void solution () {
    cin >> n >> L;
    rep (i, 1, n) {
        cin >> a[i];
    }
    cin >> Q;
    rep (i, 1, Q) cin >> qr[i];
    reb (i, n, 1) {
        rep (j, 1, n) {
            f[i & 1][j] = f[(i + 1) & 1][j + 1] + (a[i] != a[j]);
        }
        if (i <= n - L) {
            rep (j, 1, n) {
                g[(i + L) & 1][j] = g[(i + L + 1) & 1][j + 1] + (a[i + L] != a[j]);
            }
        }
        if (i <= n - L + 1) {
            rep (j, 0, n) pre[j] = 0;
            rep (j, 1, n - L + 1) {
                if (i == j) continue;
                int cur_Dist = f[i & 1][j] - g[(i + L) & 1][j + L];
                pre[cur_Dist]++;
            }
            rep (j, 1, n) pre[j] += pre[j - 1];
            rep (j, 1, Q) {
                Ans[j][i] = pre[qr[j]];
            }
        }
    }
    rep (i, 1, Q) {
        rep (j, 1, n - L + 1) cout << Ans[i][j] <<" ";
        cout <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
main () {
//    file("c");
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +12

*/

Compilation message (stderr)

lot.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main () {
      | ^~~~

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