QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375467#5116. Contestswsc2008WA 0ms161880kbC++141.9kb2024-04-03 11:09:372024-04-03 11:09:38

Judging History

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

  • [2024-04-03 11:09:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:161880kb
  • [2024-04-03 11:09:37]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=2e5+9,B=10;
ll n,q,m,a[B][N],rk[B][N],nxt[20][B][N],go[B][B][N],f[B],g[B];
//nxt[i][j][k]: starting from k, jump 2^j steps, the best rank of contest i
bool chk(ll x,ll y){
	rep(i,1,m){
		if(a[i][x]>a[i][y])return 1;
	}
	return 0;
}
mt19937 rnd(time(0));
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),m=read();
	rep(i,1,m){
		rep(j,1,n)a[i][j]=read();
	}
	// n=998,m=5;
	// rep(i,1,m){
	// 	rep(j,1,n)a[i][j]=j;
	// }
	rep(i,1,m){
		rep(j,1,n)rk[i][a[i][j]]=j;
	}
	rep(i,1,m){
		rep(j,1,m){
			rep(k,1,n)go[i][j][k]=max(go[i][j][k-1],rk[j][a[i][k]]);
		}
	}
	rep(i,1,n){
		rep(j,1,m){
			rep(k,1,m)nxt[0][j][i]=max(nxt[0][j][i],go[k][j][rk[k][i]-1]);
		}
	}
	rep(p,1,17){
		rep(i,1,m){
			rep(j,1,n){
				nxt[p][i][j]=nxt[p-1][i][j];
				rep(k,1,m)nxt[p][i][j]=max(nxt[p][i][j],nxt[p-1][i][a[k][nxt[p-1][k][j]]]);
			}
		}
	}
	q=read();
	while(q--){
		ll y=read(),x=read();
		if(chk(x,y)){
			puts("1");
			continue;
		}
		ll ans=0;
		rep(i,1,m)f[i]=rk[i][x];
		per(i,17,0){
			memset(g,0,sizeof(g));
			rep(j,1,m){
				rep(k,1,m)g[j]=max(g[j],nxt[i][j][a[k][f[k]]]);
			}
			ll fl=0;
			rep(j,1,m){
				if(chk(a[j][g[j]],y)){
					fl=1;
					break;
				}
			}
			if(!fl){
				ans|=(1<<i);
				rep(j,1,m)f[j]=g[j];
			}
		}
		if(ans>n)puts("-1");
		else write(ans+2),putchar('\n');
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 73552kb

input:

6 2
1 3 2 5 4 6
2 1 4 3 6 5
4
1 4
5 3
6 1
5 2

output:

1
2
5
3

result:

ok 4 number(s): "1 2 5 3"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 161880kb

input:

998 5
1 2 6 3 4 5 7 11 8 9 14 12 13 10 15 16 18 19 20 17 23 22 21 26 24 25 27 29 30 28 32 31 34 33 37 38 39 35 40 36 41 43 42 46 44 48 45 47 51 49 50 56 52 57 53 54 55 62 58 59 63 64 60 65 66 61 67 69 70 68 71 73 74 75 72 78 77 79 82 76 81 85 84 80 86 87 83 88 90 91 89 92 96 98 94 95 97 101 93 103 1...

output:

94
-1
1
1
1
21
1
153
-1
1
18
-1
25
1
1
1
80
1
1
1
1
-1
1
36
102
1
1
1
29
92
1
1
-1
37
37
60
1
1
1
1
1
1
1
1
16
-1
-1
1
1
-1
-1
1
1
141
1
1
77
1
60
1
1
1
3
91
1
1
-1
36
93
1
1
17
149
1
1
1
135
-1
-1
1
29
-1
-1
30
180
1
-1
-1
1
1
1
56
-1
75
25
115
121
1
-1
1
1
1
1
1
1
12
-1
1
-1
1
76
-1
128
-1
1
1
6
1...

result:

wrong answer 11th numbers differ - expected: '19', found: '18'