QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404237#6531. Base Station ConstructionMCdycWA 77ms6864kbC++231.3kb2024-05-03 16:37:182024-05-03 16:37:19

Judging History

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

  • [2024-05-03 16:37:19]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:6864kb
  • [2024-05-03 16:37:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
int solve()
{
    int n;
    cin >> n;
    map<int, int> t;
    vector<int> a(n + 2);
    vector<int> dp(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int q;
    cin >> q;
    t[0] = 0;
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        t[r] = max(t[r], l);
    }
    queue<pair<int, int>> tmp;
    for (auto it : t)
    {
        tmp.emplace(it);
    }
    tmp.push({998244353, 0});
    list<int> p;
    p.emplace_back(0);
    int l = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        while (p.front() < l)
        {
            p.pop_front();
        }
        dp[i] = a[i] + dp[p.front()];
        while (!p.empty() && dp[p.back()] >= dp[i])
        {
            p.pop_back();
        }
        p.push_back(i);
        if (i >= tmp.front().first)
        {
            l = max(l, tmp.front().second);
            tmp.pop();
        }
    }
    cout << dp[n + 1] << "\n";
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int test = 1;
    cin >> test;
    while (test--)
    {
        solve();
    }

    return 0;
}

详细

Test #1:

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

input:

2
5
3 2 4 1 100
3
1 3
2 4
5 5
5
7 3 4 2 2
3
1 4
2 3
4 5

output:

102
5

result:

ok 2 number(s): "102 5"

Test #2:

score: -100
Wrong Answer
time: 77ms
memory: 6864kb

input:

6201
12
88 78 46 95 84 98 55 3 68 42 6 18
19
6 9
10 11
12 12
8 11
8 12
2 3
2 3
1 5
9 9
7 8
6 11
2 4
12 12
2 4
2 9
7 10
8 8
1 7
6 11
5
76 27 48 66 61
2
1 4
3 5
8
64 81 20 6 86 9 4 55
1
7 7
9
1 43 18 81 11 22 9 61 83
14
5 6
2 6
5 8
1 4
9 9
9 9
7 7
2 5
8 9
5 6
4 8
5 8
9 9
6 6
10
66 41 84 7 80 31 22 96 ...

output:

141
48
4
126
303
141
23
170
159
26
153
194
136
89
84
93
287
89
124
130
148
27
1
193
194
93
108
303
236
150
79
0
46
18
24
66
83
160
108
62
0
122
156
81
115
138
54
182
126
28
171
86
311
56
262
87
121
81
86
173
0
129
75
91
90
60
0
224
62
154
77
111
194
247
211
53
52
17
203
101
308
137
177
24
204
84
146...

result:

wrong answer 10th numbers differ - expected: '139', found: '26'