Submission #810521

#	Time	Username	Problem	Language	Result	Execution time	Memory
810521		DJeniUp	Lottery (CEOI18_lot)	C++17	0 / 100	361 ms	8844 KiB

lot

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ld>pairld;

typedef pair<string,ll>pairsl;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 1000000000000007
#define eps 0.00000000001
#define A 150
#define PI 3.14159265359

ll n,l,d[10007],rs[10007][107],q,t[10007],a[10007],p[107],num[100007],o[107];

int main(){


    cin>>n>>l;
    t[0]=-1;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        t[i]=-1;
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        ll x=0;
        cin>>x;
        p[i]=x;
        o[i]=x;
        t[x]=x;
    }
    sort(o+1,o+1+q);
    for(int i=1;i<=q;i++){
        num[o[i]]=i;
    }
    t[l+1]=l+1;
    for(int i=l;i>=0;i--){
        if(t[i]==-1)t[i]=t[i+1];
        //cout<<i<<" "<<t[i]<<" "<<num[t[i]]<<endl;
    }

    for(int i=2;i<=n-l+1;i++){
        ll x=i-1;
        ll y=0;
        ll r=0;
        while(x<n){
            x++;
            y++;
            if(y>l){
                if(d[x-l]!=d[y-l])r--;
            }
            if(d[x]!=d[y])r++;
            if(y>=l){
                //cout<<"! "<<x-l+1<<" "<<y-l+1<<" "<<num[t[r]]<<endl;
                rs[x-l+1][num[t[r]]]++;
                rs[y-l+1][num[t[r]]]++;
            }
            //cout<<x<<" "<<y<<" "<<r<<endl;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=q;j++){
            rs[i][j]=rs[i][j-1]+rs[i][j];
        }
    }
    for(int i=1;i<=q;i++){
        for(int j=1;j<=n-l+1;j++){
            cout<<rs[j][num[p[i]]]<<" ";
        }
        cout<<endl;
    }

    return 0;
}

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