Submission #482940

#	Time	Username	Problem	Language	Result	Execution time	Memory
482940		Ozy	Lottery (CEOI18_lot)	C++17	100 / 100	2940 ms	12340 KiB

lot

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " =  " << a << endl
#define debugsl(a) cout << #a << " =  " << a << ", "

#define MAX 10000

lli n,l,q;
lli arr[MAX+2],normal[102];
lli res[MAX+2][102];
set<lli> x;
set<lli>::iterator it;
unordered_map<lli,lli> mapa;
vector<lli> orden;

void asigna(lli pos, lli val) {

    it = x.lower_bound(val);
    if (*it == 1000000000000) return;
    res[pos][mapa[(*it)]]++;

    //debugsl(pos);
    //debugsl(val);
    //debug(*it);
}

void solve() {

    lli val[MAX+2];
    lli a;

    val[0] = 0;
    rep(dif,1,n-l){
        rep(i,1,n-dif) {

            val[i] = val[i-1];
            if (arr[i] != arr[i+dif]) val[i]++;

            if (i >= l) {
                a = val[i] - val[i-l];
                asigna(i-l+1,a);
                asigna(i+dif-l+1,a);
            }

        }
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> l;
    rep(i,1,n) cin >> arr[i];
    cin >> q;
    rep(i,1,q) {
        cin >> normal[i];
        orden.push_back(normal[i]);
    }
    sort(orden.begin(), orden.end());
    orden.push_back(-1);

    x.insert(0);
    mapa[0] = 0;
    rep(i,0,q-1) if(orden[i] != orden[i+1]) {
        x.insert(orden[i]);
        mapa[orden[i]] = i+1;
    }
    x.insert(1000000000000);

    solve();
    rep(i,1,n) {
        rep(j,1,q) res[i][j] += res[i][j-1];
    }

    lli act;
    rep(i,1,q) {
        act = mapa[normal[i]];
        rep(j,1,n-l+1) {
            cout << res[j][act] << ' ';
        }
        cout << "\n";
    }
}

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