oj.uz

Submission #805054

# Submission time Handle Problem Language Result Execution time Memory
805054 2023-08-03T12:40:13 Z Valaki2 Lottery (CEOI18_lot) C++14
20 / 100
 22 ms 1748 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 12 ms 1304 KB Output is correct
5 Correct 21 ms 1748 KB Output is correct
6 Correct 17 ms 1492 KB Output is correct
7 Correct 21 ms 1664 KB Output is correct
8 Correct 22 ms 1640 KB Output is correct
9 Correct 14 ms 1356 KB Output is correct
10 Correct 12 ms 1364 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 13 ms 1488 KB Output is correct
13 Correct 17 ms 1712 KB Output is correct
14 Correct 16 ms 1708 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 12 ms 1304 KB Output is correct
5 Correct 21 ms 1748 KB Output is correct
6 Correct 17 ms 1492 KB Output is correct
7 Correct 21 ms 1664 KB Output is correct
8 Correct 22 ms 1640 KB Output is correct
9 Correct 14 ms 1356 KB Output is correct
10 Correct 12 ms 1364 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 13 ms 1488 KB Output is correct
13 Correct 17 ms 1712 KB Output is correct
14 Correct 16 ms 1708 KB Output is correct
15 Incorrect 15 ms 1336 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -