QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#863087	#9742. 优秀的拆分	REN5511	WA	26ms	3584kb	C++23	3.3kb	2025-01-19 13:00:24	2025-01-19 13:00:26

Judging History

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

[2025-01-19 13:00:26]
评测

测评结果：WA
用时：26ms
内存：3584kb

查看

[2025-01-19 13:00:24]
提交

answer

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
int arr[200000 + 100];
int cpy[200000 + 100];
int up[200000 + 100];
int down[200000 + 100];
int tar[200000 + 100];
stack<pair<int, int>>mem;
unordered_map<int, bool>vis;
int main()
{
    int t;
    cin >> t;
    while (t--) {
        vis.clear();
        int n;
        int lenup = 0,lendown=0,downidx=0;
        int ans = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        for (int i = 1; i <= n; i++) {
            if (arr[i] >= up[lenup]) {
                up[++lenup] = arr[i];
                mem.push({ lenup, i });
                while (mem.size()) {
                    tar[mem.top().first] = arr[mem.top().second];
                    mem.pop();
                }
            }
            else {
                int k = lower_bound(up + 1, up + lenup + 1, arr[i]) - up;
                up[k] = arr[i];
                mem.push({ k, i });
                if (k == lenup) {
                    while (mem.size()) {
                        tar[mem.top().first] = arr[mem.top().second];
                        mem.pop();
                    }
                }
            }
        }
        for (int i = 1; i <= lenup; i++) {
            vis[tar[i]] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if(vis[arr[i]]==0)
            cpy[++downidx] = arr[i];
        }
        down[0] = 1e9;
        for (int i = 1; i <= downidx; i++) {
            if (cpy[i] <= down[lendown]) {
                down[++lendown] = cpy[i];
            }
            else {
                int k = lower_bound(down + 1, down + lendown + 1, cpy[i],greater<int>()) - down;
                down[k] = cpy[i];
            }
        }
        ans = max(ans, lendown + lenup);
        ////
        lenup = 0, lendown = 0, downidx = 0;
        vis.clear();
        down[0] = 1e9;
        for (int i = 1; i <= n; i++) {
            if (arr[i] <= down[lendown]) {
                down[++lendown] = arr[i];
                mem.push({ lendown, i });
                while (mem.size()) {
                    tar[mem.top().first] = arr[mem.top().second];
                    mem.pop();
                }
            }
            else {
                int k = lower_bound(down + 1, down + lendown + 1, arr[i], greater<int>()) - down;
                down[k] = arr[i];
                mem.push({ k, i });
                if (k == lendown) {
                    while (mem.size()) {
                        tar[mem.top().first] = arr[mem.top().second];
                        mem.pop();
                    }
                }
            }
        }
        for (int i = 1; i <= lendown; i++) {
            vis[tar[i]] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[arr[i]] == 0)
                cpy[++downidx] = arr[i];
        }

        for (int i = 1; i <= downidx; i++) {
            if (cpy[i] >= up[lenup]) {
                up[++lenup] = cpy[i];
            }
            else {
                int k = lower_bound(up + 1, up + lenup + 1, cpy[i]) - up;
                up[k] = cpy[i];
            }
        }
        ans = max(ans, lendown + lenup);
        cout << ans << "\n";
    }
    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3584kb

input:

output:

4
4
5

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 26ms

memory: 3584kb

input:

20000
2
2 1
10
6 10 2 7 9 3 8 4 1 5
9
3 6 4 5 8 9 2 7 1
7
3 7 6 4 1 5 2
7
7 2 3 6 5 1 4
5
4 1 3 2 5
9
6 7 5 3 8 1 9 2 4
3
1 2 3
8
7 2 4 6 1 8 3 5
7
4 2 6 3 1 7 5
8
1 7 3 4 2 5 6 8
2
1 2
10
10 2 3 8 6 9 1 4 7 5
4
3 2 1 4
9
7 5 3 4 1 2 9 6 8
7
2 4 5 1 6 7 3
10
3 1 10 4 9 5 6 8 2 7
5
1 2 5 3 4
6
2 6 5 ...

output:

result:

wrong answer 5th lines differ - expected: '7', found: '6'