QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449905#8598. AND Масивbashkort#0 1256ms499032kbC++203.5kb2024-06-21 19:03:372024-06-21 19:03:39

Judging History

你现在查看的是最新测评结果

  • [2024-06-21 19:03:39]
  • 评测
  • 测评结果:0
  • 用时:1256ms
  • 内存:499032kb
  • [2024-06-21 19:03:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    int n, b;
    cin >> n >> b;

    vector<int> a(n);
    vector<ll> suf(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] == 0) {
            suf[i] += (i + 1);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        suf[i] += suf[i + 1];
    }

    vector<ll> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[i] += b * suf[i];
    }

    if (n <= 2000 || b <= 20) {
        const int nb = 1 << b;
        vector stk(nb, vector<int>{});
        vector<int> value(n * b), timer(n * b);

        int l = 12, r = b - l;
        int nl = (1 << l), nr = (1 << r);

        auto insert = [&](int id) {
            int x = value[id];
            int lx = x & (nl - 1);
            int ix = lx;
            int rx = x >> l << l;
            timer[id] += 1;
            while (true) {
                stk[lx + rx].push_back(id * 21 + timer[id]);
                if (lx + 1 == nl) {
                    break;
                }
                lx = (lx + 1) | ix;
            }
        };

        auto update = [&](int x, int add, int orz) {
            vector<int> now;
            int lx = x & (nl - 1);
            int rx = x >> l;
            int ix = rx;
            while (true) {
                int f = lx + (rx << l);
                now.insert(now.end(), stk[f].begin(), stk[f].end());
                stk[f].clear();
                stk[f].shrink_to_fit();
                if (rx == 0) {
                    break;
                }
                rx = (rx - 1) & ix;
            }
            for (int tt: now) {
                int i = tt / 21;
                int t = tt - i * 21;
                if (timer[i] != t) {
                    continue;
                }
                value[i] |= orz;
                ans[i % n] += add;
                insert(i);
            }
        };

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < b; ++j) {
                value[j * n + i] = 1 << j;
                insert(j * n + i);
            }
            if (a[i] != 0) {
                update(nb - 1 - a[i], i + 1, a[i]);
            }
        }
    } else {
        vector last(b, vector<int>(n + 1, -1));
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] > 0) {
                last[__lg(a[i])][i] = i;
            }
            for (int j = 0; j < b; ++j) {
                if (last[j][i] == -1) {
                    last[j][i] = last[j][i + 1];
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int s = 0; s < b; ++s) {
                int x = 1 << s;
                int t = i;
                while (x + 1 < (1 << b) && t < n) {
                    pair<int, int> mn{1e9, -1};
                    for (int u = 0; u < b; ++u) {
                        if ((x >> u & 1) == 0 && last[u][t] != -1) {
                            mn = min(mn, pair(last[u][t], u));
                        }
                    }
                    if (mn.first == 1e9) {
                        break;
                    }
                    ans[i] += mn.first + 1;
                    x |= 1 << mn.second;
                    t = mn.first + 1;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i == n - 1];
    }

    return 0;
}


詳細信息

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 10
Accepted
time: 1256ms
memory: 499032kb

input:

2000 20
251931 620255 725521 330111 783060 690627 489092 1019106 84341 631993 231500 920886 604265 342966 152434 588032 469990 805072 809795 12697 699326 433747 754394 567737 603087 199524 539078 775214 872735 454953 106496 93877 933762 36223 211878 168057 53977 782675 171782 455544 869778 47128 955...

output:

10212 4259 4815 9101 17193 17617 22629 16642 10432 10731 11766 20234 27120 17990 24654 22106 18877 14050 9217 10109 4283 9341 11741 13465 13724 9572 11200 4046 7660 7001 6512 12634 13360 10494 19745 15300 12727 17726 14188 10472 12754 7995 10571 11290 14862 19370 16785 13328 13589 17425 23190 17082 ...

result:

ok single line: '10212 4259 4815 9101 17193 176...6 39925 39961 39974 43987 18000'

Test #2:

score: -10
Memory Limit Exceeded

input:

2000 20
2080 32772 278528 256 2560 1056 528384 2056 132 144 768 98304 36864 262152 262400 81920 264192 16448 294912 786432 8194 16388 9 520 49152 2 262272 20 131584 528384 514 4352 12288 36 32800 72 16392 32 129 8 1028 131080 12288 8193 8320 528 1026 24576 8192 10240 163840 524288 262400 278528 2785...

output:

10532 10275 11389 7400 12269 14740 10975 9199 12307 10890 12090 11861 12707 12449 12586 12195 12260 14273 18795 18089 19280 21369 14169 17819 13755 16253 14945 14538 24799 24439 23275 17968 19797 19977 21225 18864 16595 21665 22140 32768 31494 29782 27849 20911 26304 21480 25191 22840 30738 26969 22...

result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

100000 20
262144 16 65536 8 256 1024 32 262144 16 262144 256 1024 1 64 2 131072 4096 2048 2 32 8192 4 2 262144 32768 1 524288 262144 262144 2048 8 64 1 2 8192 131072 256 64 8192 1 262144 4 32 4 524288 1 32768 16 64 128 8192 16 32 4096 16384 16384 4 131072 32768 16384 131072 2 16 2048 32768 16 4 4096...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #6:

score: 0
Runtime Error

input:

100000 8
98 78 5 190 79 234 162 79 118 176 115 130 10 9 233 56 97 15 148 13 46 87 92 65 150 62 50 46 159 101 48 86 203 71 29 124 23 228 55 161 240 80 139 74 251 143 167 207 183 52 50 252 17 185 40 145 167 164 227 166 172 60 182 62 173 227 232 243 251 134 109 241 44 33 217 149 51 6 110 201 242 196 23...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%