QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674464#7949. K-LotteryAestivateWA 18ms134428kbC++204.2kb2024-10-25 15:56:012024-10-25 15:56:01

Judging History

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

  • [2024-10-25 15:56:01]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:134428kb
  • [2024-10-25 15:56:01]
  • 提交

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'