QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404262 | #6531. Base Station Construction | TokaiZaopen | WA | 28ms | 12540kb | C++20 | 2.6kb | 2024-05-03 17:21:38 | 2024-05-03 17:21:40 |
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){
vector<int>::iterator x=upper_bound(c[i].begin(),c[i].end(),now);
while(*x<=n){
now=max(now,*x);
b[++cnt]={*x,i};
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: 3684kb
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: 28ms
memory: 12540kb
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:
109 48 4 21 171 40 23 170 159 95 153 169 136 68 127 42 287 14 124 98 111 27 1 98 194 90 128 303 203 50 79 57 46 18 24 66 83 160 14 31 35 110 156 81 107 138 54 230 112 28 171 79 285 146 205 68 121 81 86 114 30 129 75 91 90 99 81 201 142 77 77 111 194 185 211 53 66 17 88 101 308 106 127 24 181 139 146...
result:
wrong answer 1st numbers differ - expected: '141', found: '109'