Submission #443869

#	Time	Username	Problem	Language	Result	Execution time	Memory
443869		Haruto810198	Lottery (CEOI18_lot)	C++17	100 / 100	599 ms	12136 KiB

lot

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 10010;

int n, len;
int C;
int arr[MAX];

int q;
int dif[MAX][MAX];

pii queries[MAX];
int sat[MAX];
int res[MAX][101];
int ans[MAX][101];

void solve(int d){

    /// 0, d

    int cnt = 0;
    FOR(i, 0, len-1, 1){
        int j = i + d;
        cnt += (arr[i] != arr[j]) ? 1 : 0;
    }

    res[0][sat[cnt]]++;
    res[d][sat[cnt]]++;

    /// i, d+i

    FOR(i, 1, C-d-1, 1){
        int j = i + d;
        cnt -= (arr[i - 1] != arr[j - 1]) ? 1 : 0;
        cnt += (arr[i + len - 1] != arr[j + len - 1]) ? 1 : 0;
        res[i][sat[cnt]]++;
        res[j][sat[cnt]]++;
    }

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>len;
    FOR(i, 0, n-1, 1){
        cin>>arr[i];
    }

    C = n - len + 1;

    cin>>q;
    FOR(i, 0, q-1, 1){
        cin>>queries[i].F;
        queries[i].S = i;
    }

    sort(queries, queries+q);

    FOR(i, 0, q-1, 1){
        sat[queries[i].F] = q - i;
    }
    for(int i=n-1; i>=0; i--){
        sat[i] = max(sat[i], sat[i+1]);
    }

    FOR(d, 1, C-1, 1){
        solve(d);
    }

    FOR(i, 0, C-1, 1){
        for(int j=q-1; j>=0; j--){
            res[i][j] = res[i][j] + res[i][j+1];
        }
    }

    /*
    FOR(i, 0, C-1, 1){
        FOR(j, 0, q, 1){
            cerr<<res[i][j]<<" ";
        }
        cerr<<endl;
    }
    cerr<<endl;
    */

    FOR(i, 0, q-1, 1){
        int req = sat[queries[i].F];
        int id = queries[i].S;
        FOR(j, 0, C-1, 1){
            ans[j][id] = res[j][req];
        }
    }

    FOR(i, 0, q-1, 1){
        FOR(j, 0, C-1, 1){
            cout<<ans[j][i]<<" ";
        }
        cout<<'\n';
    }

    return 0;

}

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