QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#235205	#6334. Passport	275307894a^#	48	1510ms	39680kb	C++14	1.5kb	2023-11-02 15:57:29	2024-07-04 02:22:39

Judging History

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

[2024-07-04 02:22:39]
评测

测评结果：48
用时：1510ms
内存：39680kb

查看

[2023-11-02 15:57:29]
提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=3e3+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,L[N],R[N],q,ans[N],dp[N][N];
int mx[N][20],mi[N][20];
int qx(int x,int y){int d=__lg(y-x+1);return max(mx[x][d],mx[y-(1<<d)+1][d]);}
int qi(int x,int y){int d=__lg(y-x+1);return min(mi[x][d],mi[y-(1<<d)+1][d]);}
int main(){
	int i,j,h;scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
	for(i=n;i;i--){
		for(mi[i][0]=L[i],j=1;i+(1<<j)-1<=n;j++) mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
		for(mx[i][0]=R[i],j=1;i+(1<<j)-1<=n;j++) mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
	}
	Me(dp,0x3f);Me(ans,0x3f);
	dp[1][n]=0;
	for(i=n-1;i;i--){
		for(j=1;j<=n;j++) ans[j]=min(ans[j],dp[L[j]][R[j]]+1);
		for(j=1;j+i-1<=n;j++) {
			int l=j,r=j+i-1;
			for(h=l;h<=r;h++) dp[l][r]=min(dp[l][r],ans[h]);
			dp[l][r]=min(dp[l][r],min(dp[qi(l,r)][r],dp[l][qx(l,r)])+1);
			// cerr<<l<<' '<<r<<' '<<dp[l][r]<<'\n';
		}
	}
	int q;scanf("%d",&q);
	while(q--){
		int x;scanf("%d",&x);
		printf("%d\n",ans[x]>n+1?-1:ans[x]);
	}
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Runtime Error

Test #1:

score: 6

Accepted

time: 4ms

memory: 39132kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 6

Accepted

time: 3ms

memory: 39620kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Runtime Error

input:

output:

result:

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 0ms

memory: 39256kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 16

Accepted

time: 0ms

memory: 39132kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 16

Accepted

time: 0ms

memory: 39128kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 16

Accepted

time: 0ms

memory: 39088kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 16

Accepted

time: 0ms

memory: 39180kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 16

Accepted

time: 0ms

memory: 39180kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 16

Accepted

time: 8ms

memory: 39324kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 16

Accepted

time: 4ms

memory: 39208kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 16

Accepted

time: 3ms

memory: 39180kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 16

Accepted

time: 0ms

memory: 39316kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 16

Accepted

time: 8ms

memory: 39136kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 1220ms

memory: 39524kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 24

Accepted

time: 1470ms

memory: 39540kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 24

Accepted

time: 1500ms

memory: 39576kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 24

Accepted

time: 1380ms

memory: 39596kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 24

Accepted

time: 1510ms

memory: 39568kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 24

Accepted

time: 1498ms

memory: 39624kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 24

Accepted

time: 1503ms

memory: 39532kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 24

Accepted

time: 1506ms

memory: 39492kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 24

Accepted

time: 1501ms

memory: 39680kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 1350ms

memory: 39664kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 8

Accepted

time: 1505ms

memory: 39492kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 8

Accepted

time: 1505ms

memory: 39540kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 8

Accepted

time: 1494ms

memory: 39564kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 8

Accepted

time: 1364ms

memory: 39592kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 0

Runtime Error

Test #33:

score: 0

Runtime Error

input: