Submission #805054

#	Time	Username	Problem	Language	Result	Execution time	Memory
805054		Valaki2	Lottery (CEOI18_lot)	C++14	20 / 100	22 ms	1748 KiB

lot

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 10000;

int n, l, q;
int v[1 + maxn];
int interval_count;
vector<vector<int> > indices, blocks;
int thelog;

vector<int> x, y;
int len;

bool cmp(const int &a, const int &b) {
    if(x[a] < x[b]) {
        return true;
    }
    if(x[a] > x[b]) {
        return false;
    }
    return (y[(a + len) % n] < y[(b + len) % n]);
}

void do_step(vector<int> &idx, vector<int> &block) {
    sort(idx.begin(), idx.end(), cmp);
    for(int i = 1; i < n; i++) {
        int j1 = idx[i], j2 = idx[i - 1];
        if(!cmp(j2, j1) && !cmp(j1, j2)) {
            block[j1] = block[j2];
        } else {
            block[j1] = block[j2] + 1;
        }
    }
}

bool easy_cmp(const int &a, const int &b) {
    return v[a + 1] < v[b + 1];
}

void solve() {
    cin >> n >> l;
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    int k0;
    cin >> q >> k0;
    interval_count = n - l + 1;
    while((1 << thelog) <= l) {
        thelog++;
    }
    vector<int> all_indices(n);
    for(int i = 0; i < n; i++) {
        all_indices[i] = i;
    }
    indices.assign(thelog, all_indices);
    blocks.assign(thelog, vector<int> (n, 0));
    sort(indices[0].begin(), indices[0].end(), easy_cmp);
    for(int i = 1; i < n; i++) {
        if(v[indices[0][i] + 1] == v[indices[0][i - 1] + 1]) {
            blocks[0][indices[0][i]] = blocks[0][indices[0][i - 1]];
        } else {
            blocks[0][indices[0][i]] = blocks[0][indices[0][i - 1]] + 1;
        }
    }
    for(int i = 1; i < thelog; i++) {
        len = (1 << (i - 1));
        x = y = blocks[i - 1];
        do_step(indices[i], blocks[i]);
    }
    vector<int> idx = all_indices, block(n, 0);
    bool was = false;
    for(int i = 0; i < thelog; i++) {
        if(l & (1 << i)) {
            if(!was) {
                was = true;
                idx = indices[i];
                block = blocks[i];
                len = (1 << i);
            } else {
                x = block;
                y = blocks[i];
                do_step(idx, block);
                len += (1 << i);
            }
        }
    }
    vector<int> ans(1 + n, 0);
    vector<int> block_cnt(n, 0);
    for(int i = 0; i < n; i++) {
        if(i + l <= n) {
            block_cnt[block[i]]++;
        }
    }
    for(int i = 1; i <= interval_count; i++) {
        cout << block_cnt[block[i - 1]] - 1 << " ";
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
6 2
1 2 1 3 2 1
1
0
*/

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