QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674462#7949. K-LotteryAestivateWA 1385ms183384kbC++204.2kb2024-10-25 15:54:322024-10-25 15:54:33

Judging History

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

  • [2024-10-25 15:54:33]
  • 评测
  • 测评结果:WA
  • 用时:1385ms
  • 内存:183384kb
  • [2024-10-25 15:54:32]
  • 提交

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=1000000000163;

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 = 137;
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;
            now+=po[j]*g, 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: 100
Accepted
time: 7ms
memory: 133096kb

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: 3ms
memory: 133408kb

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: 0ms
memory: 134864kb

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: -100
Wrong Answer
time: 1385ms
memory: 183384kb

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:

0

result:

wrong answer 1st lines differ - expected: '1 5001 2 5002 3 5003 4 5004 5 ... 4998 9998 4999 9999 5000 10000', found: '0'