QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404260 | #6531. Base Station Construction | TokaiZaopen | WA | 23ms | 12736kb | C++20 | 2.6kb | 2024-05-03 17:16:05 | 2024-05-03 17:16:06 |
Judging History
answer
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<set>
#include<functional>
#include<map>
#include<bitset>
#include<deque>
#include<math.h>
#include<iomanip>
#include<unordered_map>
// 我好菜啊 QAQ
#define int ll
#define lll __int128_t
#define ST int T;scanf("%lld",&T);while(T--){
#define STF int T;T=read();while(T--){
#define ED }
#define foi(N) for(int i=1;i<=N;i++)
#define foj(N) for(int j=1;j<=N;j++)
#define fok(N) for(int k=1;k<=N;k++)
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,l,r) for(int i=l;i>=r;i--)
#define YES printf("YES\n")
#define NO printf("NO\n")
#define W 64
#define CLR(Q) while(!Q.empty()) Q.pop_front();
#define lm(N) (1LL<<N)
#define FAST_IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
const int inf=2e18;
const int mod=998244353;
namespace FAST{
char buf[1<<20], *p1, *p2;
char gc() { return p1 == p2 ? p2 = buf + fread(p1 = buf, 1, 1<<20, stdin), (p1 == p2) ? EOF : *p1++ : *p1++; }
inline int read(int f = 1, char c = gc(), int x = 0) {
while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
return f * x;
}
} using FAST::read;
using namespace std;
/*
1
4
1 4 1 4
2
1 1
3 3
*/
struct sss{
int l;
int r;
};
struct boom{
int p;
int num;
};
int n;
int a[500010];
int m;
sss b[500010];
vector<int> c[500010];
int dp[500010];
signed main()
{
STF
n=read();
foi(n) a[i]=read();
m=read();
foi(n){
c[i].clear();
c[i].push_back(inf);
}
foi(m){
int l,r;
l=read();
r=read();
c[r].push_back(l);
}
foi(n) sort(c[i].begin(),c[i].end());
int cnt=0;
int now=0;
foi(n){
int x=*upper_bound(c[i].begin(),c[i].end(),now);
if(x>n) continue;
b[++cnt]={x,i};
now=x;
}
b[0]={0,0};
// b[cnt+1]={n+1,n+1};
b[cnt+1]={b[cnt].r+1,n+1};
a[n+1]=0;
deque<boom> q;
CLR(q);
int st=1;
while(st<b[1].l) st++;
int p=1;
dp[st-1]=0;
q.push_back({st-1,0});
fo(i,st,n+1){
if(i>b[p].r){
while(!q.empty() && q.front().p<b[p].l) q.pop_front();
fo(j,max(b[p].l,b[p-1].r+1),b[p].r){
while(!q.empty() && q.back().num>=dp[j]) q.pop_back();
q.push_back({j,dp[j]});
}
p++;
// if(p>cnt){
// dp[n+1]=q.front().num;
// break;
// }
}
dp[i]=q.front().num+a[i];
}
// foi(cnt) printf("??? %lld %lld ???\n",b[i].l,b[i].r);
// foi(n) printf("/// %lld %lld ///\n",i,dp[i]);
printf("%lld\n",dp[n+1]);
ED
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3696kb
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: 23ms
memory: 12736kb
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 82 229 141 23 170 159 95 153 169 136 68 230 58 287 14 124 130 111 27 1 193 194 47 239 303 140 50 177 57 46 18 24 66 83 160 24 31 35 122 156 81 107 138 54 230 112 28 171 86 240 244 205 68 302 81 86 114 30 129 40 91 90 179 81 153 142 77 75 111 174 185 211 53 66 17 88 101 308 106 177 24 188 13...
result:
wrong answer 4th numbers differ - expected: '126', found: '82'