QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#674382 | #7949. K-Lottery | Aestivate | WA | 1891ms | 129232kb | C++20 | 4.0kb | 2024-10-25 15:29:36 | 2024-10-25 15:29:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
const int mol=998244353;
const int N = 1e6+5;
int inv[N], po[N];
struct Seg{
int seg[N*4]={0},la[N*4]={0}, seg2[N*4];
void init(int n){
for(int i=1;i<=n*4;i++) seg[i]=0, la[i]=0, seg2[i]=0;
}
void push(int ind){
int t=la[ind];la[ind]=0;
la[ind*2]+=t,la[ind*2+1]+=t,seg[ind*2]*=inv[t],seg[ind*2+1]*=inv[t];
seg[ind*2]%=mol, seg[ind*2+1]%=mol;
}
void upd(int l,int r,int l1,int r1,int val,int ind){
if(l1<=l&&r<=r1) {
seg[ind]*=inv[val], seg[ind]%=mol;
la[ind]+=val;
return;
}
int mid=l+r>>1;
if(la[ind]) push(ind);
if(r1<=mid) upd(l,mid,l1,r1,val,ind*2);
else if(l1>mid) upd(mid+1,r,l1,r1,val,ind*2+1);
else{
upd(l,mid,l1,r1,val,ind*2);upd(mid+1,r,l1,r1,val,ind*2+1);
}
seg[ind]=(seg[ind*2]+seg[ind*2+1])%mol;
}
void u2(int l, int r, int xx, int val, int ind){
if(l==r){
seg[ind]=val;
if(val==0)
seg2[ind]=0;
else seg2[ind]=1;
return;
}
int mid=l+r>>1;
if(la[ind]) push(ind);
if(xx<=mid) u2(l, mid, xx, val, ind*2);
else u2(mid+1, r, xx, val, ind*2+1);
seg[ind]=(seg[ind*2]+seg[ind*2+1])%mol;
seg2[ind]=(seg2[ind*2]+seg2[ind*2+1]);
}
int val(int l,int r,int l1,int r1,int ind){
if(l1>r1) return 0;
if(l1<=l&&r<=r1) return seg[ind];
int mid=l+r>>1;
if(la[ind]) push(ind);
if(r1<=mid) return val(l,mid,l1,r1,ind*2);
else if(l1>mid) return val(mid+1,r,l1,r1,ind*2+1);
else return (val(l,mid,l1,r1,ind*2)+val(mid+1,r,l1,r1,ind*2+1))%mol;
seg[ind]=(seg[ind*2]+seg[ind*2+1])%mol;
}
int big(int l, int r, int xx, int ind){
if(l==r) return 0;
int mid=l+r>>1;
if(xx<=mid) return big(l, mid, xx, ind*2);
else return seg2[ind*2]+big(mid+1, r, xx, ind*2+1);
}
}iu;
const int cc = 137;
int ff(int g, int h){
int bas=g, ans=1;
while(h){
if(h&1) ans*=bas, ans%=mol;
bas*=bas, bas%=mol;
h>>=1;
}
return ans;
}
void solve(){
int k, m, n;
cin>>k>>m>>n;
po[0]=1;
inv[0]=1;
for(int i=1;i<=n;i++) po[i]=po[i-1]*cc%mol;
int iv=ff(cc, mol-2);
for(int i=1;i<=n;i++) inv[i]=inv[i-1]*iv%mol;
map<int, vector<int>>ans;
for(int i=1;i<=m;i++){
int now=0;
vector<int>tot;
for(int j=1;j<=k;j++){
int g;
cin>>g;
now+=g*po[j], now%=mol;
tot.pb(g);
}
ans[now]=tot;
}
vector<int>all, all2;
for(int i=1;i<=n;i++){
int g;
cin>>g;
all.pb(g);
}
all2=all;
int nowval=0;
iu.init(n);
sort(all2.begin(), all2.end());
for(int i=0;i<n;i++){
int g=lower_bound(all2.begin(), all2.end(), all[i])-all2.begin()+1;
if(i>=k){
int gg=lower_bound(all2.begin(), all2.end(), all[i-k])-all2.begin()+1;
int vv=iu.val(1, n, gg+1, n, 1);
nowval-=vv;
nowval=(nowval+mol)%mol;
int c2=iu.big(1, n, gg, 1);
nowval-=(c2+1)*po[1]%mol, nowval=(nowval+mol)%mol;
iu.u2(1, n, gg, 0, 1);
iu.upd(1, n, 1, n, 1, 1);
nowval*=inv[1], nowval%=mol;
}
int cc=iu.big(1, n, g, 1);
int v2=iu.val(1, n, g+1, n, 1);
nowval+=v2, nowval%=mol;
nowval+=(cc+1)*po[min(i+1, k)], nowval%=mol;
iu.u2(1, n, g, po[min(i+1, k)], 1);
if(i+1<k) continue;
if(ans.count(nowval)){
for(int ii: ans[nowval]) cout<<ii<<" ";
return;
}
}
cout<<"0\n";
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
// int t;
// cin>>t;
// while(t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 71504kb
input:
3 2 10 1 2 3 1 3 2 20 35 10 7 99 53 72 33 88 16
output:
1 3 2
result:
ok single line: '1 3 2 '
Test #2:
score: 0
Accepted
time: 14ms
memory: 70932kb
input:
4 5 10 1 2 3 4 1 2 4 3 3 4 1 2 4 1 2 3 4 2 3 1 19 31 9 1 89 48 63 30 78 12
output:
4 2 3 1
result:
ok single line: '4 2 3 1 '
Test #3:
score: 0
Accepted
time: 3ms
memory: 71212kb
input:
3 3 7 1 3 2 2 3 1 2 1 3 11 22 33 44 55 66 77
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 800ms
memory: 129148kb
input:
10000 10 1000000 1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...
output:
1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5037 38 5038 39 50...
result:
ok single line: '1 5001 2 5002 3 5003 4 5004 5 ...4998 9998 4999 9999 5000 10000 '
Test #5:
score: 0
Accepted
time: 1879ms
memory: 129172kb
input:
10000 10 1000000 7171 4541 8189 3253 6694 2078 7384 1786 7847 5040 953 4126 4806 3532 7875 8531 3543 2706 8565 1509 2092 4125 6110 5251 6314 4574 6726 8900 9328 8639 3990 5234 9012 5023 3289 2825 8038 3593 2249 337 6252 3831 7967 3839 2815 540 3754 1009 8772 2939 2845 5067 6587 2615 375 7252 9940 18...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 740ms
memory: 129132kb
input:
10000 10 1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 1859ms
memory: 129072kb
input:
10000 10 1000000 3 7 8 1 4 10 2 5 9 6 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1891ms
memory: 129232kb
input:
10000 10 1000000 1 3 7 10 6 4 9 8 2 5 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1737ms
memory: 128988kb
input:
100 1000 1000000 34 82 39 96 30 85 83 16 8 31 51 63 76 49 3 7 58 17 42 94 41 9 11 47 89 6 86 19 100 77 37 93 40 15 36 71 23 46 48 55 2 92 64 18 22 21 12 72 1 99 70 81 56 57 53 62 50 35 65 43 73 60 97 24 4 98 20 90 26 68 66 25 74 87 14 67 45 95 33 32 52 29 5 88 54 13 91 10 59 80 28 38 78 61 79 75 69 ...
output:
0
result:
ok single line: '0'
Test #10:
score: -100
Wrong Answer
time: 449ms
memory: 129060kb
input:
100 1000 1000000 45 10 54 59 1 86 77 71 61 27 62 26 39 23 21 88 24 85 32 66 53 70 78 90 22 7 72 35 42 76 5 14 16 15 17 51 38 2 46 20 41 56 28 4 57 49 25 97 64 44 8 58 96 29 63 52 89 33 18 94 69 36 43 74 98 40 73 87 65 11 100 60 93 30 13 84 19 80 34 79 31 48 37 12 99 82 92 3 9 67 83 47 50 68 55 91 6 ...
output:
75 40 72 69 92 79 1 8 87 76 9 17 14 45 89 74 39 34 30 47 20 10 43 94 56 85 19 98 33 46 95 59 4 16 12 22 60 25 37 29 41 84 32 6 51 48 23 24 18 50 100 81 99 11 44 21 5 83 66 82 80 62 67 91 63 68 64 78 65 52 55 53 86 15 96 7 28 58 26 73 49 54 36 13 35 90 77 42 88 2 31 38 70 93 3 71 27 97 61 57
result:
wrong answer 1st lines differ - expected: '0', found: '75 40 72 69 92 79 1 8 87 76 9 ...2 31 38 70 93 3 71 27 97 61 57 '