Submission #1199947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199947		Zbyszek99	Lottery (CEOI18_lot)	C++17	0 / 100	278 ms	4372 KiB

lot

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int arr[10'001];
int dp[2][10'001];
int query_ans[10'001][101];
int query_ind[10'001];
int rel_ind[101];
vector<pii> queries;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    int n,l;
    cin >> n >> l;
    rep(i,n) cin >> arr[i];
    int q;
    cin >> q;
    rep(i,q)
    {
        int x;
        cin >> x;
        queries.pb({x,i});
    }
    sort(all(queries));
    rep(i,q) rel_ind[queries[i].ss] = i; 
    rep(i,q) query_ind[i] = q;
    rep(i,siz(queries))
    {
        int prev = -1;
        if(i != 0) prev = queries[i-1].ff;
        rep2(j,prev+1,queries[i].ff) query_ind[j] = i;
    }
    for(int i = n-l; i >= 0; i--)
    {
        rep(k,n) swap(dp[0][k],dp[1][k]);
        for(int j = n-l; j >= 0; j--)
        {
            if(i == n-l || j == n-l)
            {
                int cnt = 0;
                rep(k,l)
                {
                    if(arr[i+k] != arr[j+k]) cnt++;
                }
                dp[1][j] = cnt;
            }
            else
            {
                dp[1][j] = dp[0][j+1] - (arr[i+l] != arr[j+l] ? 1 : 0) + (arr[i] != arr[j] ? 1 : 0);
            }
           // cout << i << " " << j << " " << dp[1][j] << " " << query_ind[dp[1][j]] << " query\n";
            query_ans[i][query_ind[dp[1][j]]]++;
        }
        rep2(j,1,q-1)
        {
            query_ans[i][j] += query_ans[i][j-1];
        }
    }
    rep(i,q)
    {
        rep(j,n-l+1)
        {
            cout << query_ans[j][rel_ind[i]]-1 << " ";
        }
        cout << "\n"; 
    }
}

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