QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#674464 | #7949. K-Lottery | Aestivate | WA | 18ms | 134428kb | C++20 | 4.2kb | 2024-10-25 15:56:01 | 2024-10-25 15:56:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define pb push_back
#define F first
#define S second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
const ll mol=100000000003;
const int N = 1e6+5;
ll inv[N], po[N];
struct Seg{
ll seg[N*4]={0},la[N*4]={0};
int 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]);
}
ll 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 = 10357;
ll ff(ll g, ll h){
ll 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;
ll iv=ff(cc, mol-2);
for(int i=1;i<=n;i++) inv[i]=inv[i-1]*iv%mol;
map<ll, vector<int>>ans;
for(int i=1;i<=m;i++){
ll now=0;
vector<int>tot;
for(int j=1;j<=k;j++){
int g;
cin>>g;
ll nn=g;
now+=nn*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;
ll 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;
ll 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);
ll 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 18ms
memory: 134428kb
input:
3 2 10 1 2 3 1 3 2 20 35 10 7 99 53 72 33 88 16
output:
0
result:
wrong answer 1st lines differ - expected: '1 3 2', found: '0'