QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404260#6531. Base Station ConstructionTokaiZaopenWA 23ms12736kbC++202.6kb2024-05-03 17:16:052024-05-03 17:16:06

Judging History

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

  • [2024-05-03 17:16:06]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:12736kb
  • [2024-05-03 17:16:05]
  • 提交

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'