Submission #464618

#	Time	Username	Problem	Language	Result	Execution time	Memory
464618		idk321	Lottery (CEOI18_lot)	C++17	45 / 100	365 ms	65540 KiB

lot

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

const int N = 10005;
int tree[4 * N];
int n, l;
vector<vector<int>> diff;
bool vis[N][N];
void add(int from, int to, int a, int b, int node) {
    if (from <= a && b <= to) {
        tree[node]++;
        return;
    }

    int mid = (a + b) / 2;
    if (from <= mid) add(from, to, a, mid, node * 2);
    if (to > mid) add(from, to, mid + 1, b, node * 2 +1);
}

int getNum(int i, int a, int b, int node) {
    if (a == b) return tree[node];

    int mid = (a + b) / 2;
    int res = tree[node];
    if (i <= mid) return getNum(i, a, mid, node * 2) + res;
    return res + getNum(i, mid + 1, b, node * 2 + 1);
}

int getSumFor(int i, int j) {
    if (vis[i][j]) return diff[i][j];
    vis[i][j] = true;
    if (i - 1 >= 0 && j - 1 >= 0) {
        diff[i][j] += getSumFor(i - 1, j - 1);
    }
    return diff[i][j];
}

int getDist(int i, int j) {
    int cur = diff[i + l - 1][j + l - 1];
    if (i != 0 && j != 0) cur -= diff[i - 1][j - 1];
    return cur;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> n >> l;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    int q;
    cin >> q;
    vector<int> k(q);
    for (int i = 0; i < q; i++) cin >> k[i];
    diff.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) if (v[i] != v[j]) diff[i][j] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            getSumFor(i, j);
        }
    }



    for (int q1 = 0; q1 < q; q1++) {
        for (int i = 0; i <= n - l; i++) {
            int cur = 0;
            for (int j = 0; j <= n - l; j++ ) {
                if (j == i) continue;
                if (getDist(i, j) <= k[q1]) cur++;
            }
            cout << cur << " ";
        }
        cout << "\n";
    }
}
/*
6 2
1 2 1 3 2 1
2
1
2 */

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