Submission #1108414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108414		koukirocks	Lottery (CEOI18_lot)	C++17	100 / 100	344 ms	12140 KiB

lot

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

vector<pii> qry;

int main() {
    speed;
    int n,l;
    cin>>n>>l;
    vector<int> a(n+1);
    for (int i=0;i<n;i++) {
        cin>>a[i];
    }
    int q;
    cin>>q;
    qry.resize(q);
    for (int i=0;i<q;i++) {
        cin>>qry[i].F;
        qry[i].S=i;
    }
    vvector<int> ans(q,vector<int>(n));
    sort(all(qry),[&](pii a,pii b){
        return a.F<b.F;
    });
    vector<int> ntk(l+1);
    int id=q;
    for (int i=l;i>=0;i--) {
        while (id>0 and qry[id-1].F>=i) id--;
        ntk[i]=id;
    }
    for (int g=1;g+l<=n;g++) {
        short now=0;
        for (int i=0;i<l;i++) {
            if (a[i]!=a[i+g]) now++;
        }
        for (int i=0;i+g+l<=n;i++) {
            if (ntk[now]!=q) {
                ans[ntk[now]][i]++;
                ans[ntk[now]][i+g]++;
            }
            now-=(a[i]!=a[i+g]);
            now+=(a[i+l]!=a[i+g+l]);
        }
    }
    for (int i=0;i<=n-l;i++) {
        for (int j=1;j<q;j++) ans[j][i]+=ans[j-1][i];
    }
    vvector<int> aa(q,vector<int>(n-l+1));
    for (int i=0;i<q;i++) {
        for (int j=0;j<=n-l;j++) aa[qry[i].S][j]=ans[i][j];
    }
    for (int i=0;i<q;i++) {
        for (int j=0;j<=n-l;j++) cout<<aa[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

/*
10 10
2 34 545 56 3 3 65 2 7 6
*/

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