QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605586#7859. Bladestormucup-team4906#WA 26ms5612kbC++204.8kb2024-10-02 18:04:372024-10-02 18:04:37

Judging History

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

  • [2024-10-02 18:04:37]
  • 评测
  • 测评结果：WA
  • 用时：26ms
  • 内存：5612kb
查看
  • [2024-10-02 18:04:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define N 110000
#define M 350

int n, k;
int p[N];
namespace S1
{
    int bel[N], L[M], R[M];
    int nxt[N], w[N];
    int fir[M];
    int mxHP;
    int BL, cnt;
    bool vst[N];
    void clear()
    {
        for (int i = 1; i <= n; i ++) nxt[i] = vst[i] = w[i] = bel[i] = 0;
        for (int i = 1; i <= cnt; i ++) L[i] = R[i] = fir[i] = 0;
        mxHP = BL = cnt = 0;
    }
    void upd(int t)
    {
        int l = L[t], r = R[t];
        int nx = n + 1;
        for (int i = t + 1; i <= cnt; i ++) if (fir[i]) {nx = fir[i]; break;}
        for (int i = r; i >= l; i --)
        {
            if (nx - i > k)
            {
                if (nx > r) nxt[i] = nx, w[i] = 1;
                else nxt[i] = nxt[nx], w[i] = w[nx] + 1;
            }
            else
            {
                if (i + k > r)nxt[i] = min(i + k, n + 1), w[i] = 1;
                else nxt[i] = nxt[i + k], w[i] = w[i + k] + 1;
            }
            if (vst[i]) nx = i;
        }
        // cout << "??:" << l << ' ' << r << " " << t << endl;
        // for (int i = l; i <= r; i ++) cout << nxt[i] << ' '; cout << endl;
        // for (int i = l; i <= r; i ++) cout << w[i] << ' '; cout << endl;
        // cout << endl;
    }
    int calc()
    {
        int now = 0, ans = 0;
        int tnxt = 0;
        for (int i = 1; i <= cnt; i ++) if (fir[i]) {tnxt = fir[i]; break;}
        now = max(k, tnxt); ans = 1;
        while (now < mxHP)
        {
            int nowr = 0;
            if (nxt[now] >= mxHP)
            {
                for (int i = now + 1;; i ++) if (vst[i])
                {
                    nowr = i; break;
                }
                nowr = max(nowr, now + k);
                now = nowr; ans ++; continue;
            }
            ans += w[now]; now = nxt[now];
            continue;
        }
        // cout << "EEE:" << ans << endl;
        return ans;
    }
    void sol()
    {
        BL = cnt = sqrt(n);
        for (int i = 1; i <= cnt; i ++)
        {
            L[i] = R[i - 1] + 1;
            R[i] = L[i] + BL - 1;
        }
        if (R[cnt] < n) {++ cnt; L[cnt] = R[cnt - 1] + 1; R[cnt] = n;}
        for (int i = 1; i <= cnt; i ++)
        {
            for (int j = L[i]; j <= R[i]; j ++) bel[j] = i;
        }
        for (int i = cnt; i >= 1; i --) upd(i);
        
        for (int i = 1; i <= n; i ++)
        {
            int x = p[i];
            if (fir[bel[x]]) fir[bel[x]] = min(fir[bel[x]], x);
            else fir[bel[x]] = x;
            mxHP = max(mxHP, x);
            vst[x] = 1; upd(bel[x]); 
            if (bel[x] > 1)upd(bel[x] - 1);

            cout << calc() << ' ';
        }
        cout << '\n';
        clear();
    }
}
namespace S2
{
    bool vst[N];
    int bel[N], L[M], R[M];
    int s[N], tag[M];
    int BL, cnt;
    int mxHP;
    void clear()
    {
        for (int i = 1; i <= n; i ++) vst[i] = bel[i] = s[i] = 0;
        for (int i = 1; i <= cnt; i ++)tag[i] = L[i] = R[i] = 0;
        BL = cnt = mxHP = 0;
    }
    void add(int x)
    {
        int t = bel[x];
        for (int i = x; i <= R[t]; i ++)s[i] ++;
        for (int i = t + 1; i <= cnt; i ++)tag[i] ++;
    }
    int qry(int x)
    {
        if (x == 0)return 0;
        return s[x] + tag[bel[x]];
    }
    int qry(int l, int r) 
    {
        r = min(r, n);
        return qry(r) - qry(l - 1);
    }
    int calc()
    {
        int now = 0, ans = 0;
        while (now < mxHP)
        {
            int rnow = now + k; ans ++;
            if (qry(now + 1, rnow)) {now = rnow; continue;}
            else 
            {
                while (!vst[rnow]) rnow ++;
                now = rnow; continue;
            }
        }
        return ans;
    }
    void sol()
    {
        BL = cnt = sqrt(n);
        for (int i = 1; i <= cnt; i ++)
        {
            L[i] = R[i - 1] + 1;
            R[i] = L[i] + BL - 1;
        }
        if (R[cnt] < n) {++ cnt; L[cnt] = R[cnt - 1] + 1; R[cnt] = n;}
        for (int i = 1; i <= cnt; i ++)
        {
            for (int j = L[i]; j <= R[i]; j ++) bel[j] = i;
        }
        for (int i = 1; i <= n; i ++)
        {
            mxHP = max(mxHP, p[i]);
            add(p[i]);
            vst[p[i]] = 1;
            cout << calc() << ' ';
        }
        cout << '\n';
        clear();
    }
}
void sol()
{
    cin >> n >> k;

    for (int i = 1; i <= n; i ++) cin >> p[i]; 

    if (k < sqrt(n)) S1::sol();
    else S2::sol();
    // S2::sol();
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) sol();
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5612kb

input:

3
7 2
4 7 3 6 1 2 5
11 3
10 7 4 9 6 8 5 1 3 2 11
9 2
1 2 3 7 8 9 4 5 6

output:

1 2 3 3 4 4 4 
1 2 3 3 3 3 3 4 4 4 4 
1 1 2 3 4 4 4 5 5

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 26ms
memory: 3748kb

input:

40319
1 1
1
2 1
1 2
2 1
2 1
2 2
1 2
2 2
2 1
3 1
1 2 3
3 1
1 3 2
3 1
2 1 3
3 1
2 3 1
3 1
3 1 2
3 1
3 2 1
3 2
1 2 3
3 2
1 3 2
3 2
2 1 3
3 2
2 3 1
3 2
3 1 2
3 2
3 2 1
3 3
1 2 3
3 3
1 3 2
3 3
2 1 3
3 3
2 3 1
3 3
3 1 2
3 3
3 2 1
4 1
1 2 3 4
4 1
1 2 4 3
4 1
1 3 2 4
4 1
1 3 4 2
4 1
1 4 2 3
4 1
1 4 3 2
4 1
...

output:

1 
1 2 
1 2 
1 1 
1 1 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 1 2 
1 2 2 
1 1 2 
1 2 2 
1 2 2 
1 2 2 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4...

result:

wrong answer 5536th lines differ - expected: '1 2 3 4 5 6 7', found: '1 2 3 4 4 6 7 '
English 繁體中文 简体中文

Server Time: 2024-12-03 04:24:38 | OpenSource Project