QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404262#6531. Base Station ConstructionTokaiZaopenWA 28ms12540kbC++202.6kb2024-05-03 17:21:382024-05-03 17:21:40

Judging History

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

  • [2024-05-03 17:21:40]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:12540kb
  • [2024-05-03 17:21:38]
  • 提交

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'