QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167720#7108. CouleurDelay_for_five_minutesWA 2ms7564kbC++145.2kb2023-09-07 16:50:172023-09-07 16:50:18

Judging History

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

  • [2023-09-07 16:50:18]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7564kb
  • [2023-09-07 16:50:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
const int maxn=100000+10,B=224;
int f[B+10][B+10],num[B+10],g[maxn][B+10];
int tree[maxn];
int a[maxn],belong[maxn],b[maxn],c[maxn],d[maxn],sum[maxn],cnt[maxn];
int i,j,k,l,r,s,t,n,tot,top;
ll ans,now;

bool cmp(int x,int y){
    return a[x]<a[y];
}
int lowbit(int x){
    return x&-x;
}
void change(int x){
    while (x>0){
        tree[x]++;
        x-=lowbit(x);
    }
}
int query(int x){
    int t=0;
    while (x<=n){
        t+=tree[x];
        x+=lowbit(x);
    }
    return t;
}
int work(int top,int tot){
    int i=1,j=1,t=0;
    while (i<=top&&j<=tot){
        if (c[i]<=d[j]) i++;
        else{
            j++;
            t+=top-i+1;
        }
    }
    return t;
}
ll ask(int x,int l,int r){
    int i,t=sum[r]-(l==(x-1)*B+1?0:sum[l-1]);
    top=0;
    fo(i,(x-1)*B+1,min(x*B,n))
        if (b[i]<l) c[++top]=a[b[i]];
    tot=0;
    fo(i,(x-1)*B+1,min(x*B,n))
        if (b[i]>=l&&b[i]<=r) d[++tot]=a[b[i]];
    t-=work(top,tot);
    return t;
}
void init(){
    for(int i = 1;i <= n;i++) {
        tree[i] = 0;b[i] = c[i] = d[i] = sum[i] = cnt[i] = belong[i] = num[i] = 0;
    }
    s = t = tot = top = now = k = 0;

    fo(i,1,n) b[i]=a[i];
    sort(b+1,b+n+1);
    top=unique(b+1,b+n+1)-b-1;
    fo(i,1,n) a[i]=lower_bound(b+1,b+top+1,a[i])-b;
    fo(i,1,n) belong[i]=(i-1)/B+1;
    fo(i,1,n) b[i]=i;
    sort(b+1,b+n+1,cmp);
    i=1;
    while (i<=n){
        t=a[b[i]];
        j=i;
        while (i<=n&&a[b[i]]==t){
            fo(k,belong[b[i]]+1,belong[n]) g[b[i]][k]=num[k];
            i++;
        }
        fo(k,j,i-1) num[belong[b[k]]]++;
    }
    fo(i,1,belong[n]) num[i]=0;
    reverse(b+1,b+n+1);
    i=1;
    while (i<=n){
        t=a[b[i]];
        j=i;
        while (i<=n&&a[b[i]]==t){
            fo(k,1,belong[b[i]]-1) g[b[i]][k]=num[k];
            i++;
        }
        fo(k,j,i-1) num[belong[b[k]]]++;
    }
    fo(j,1,belong[n])
        fd(i,(j-1)*B,1)
            if (i%B!=0) g[i][j]+=g[i+1][j];
    fo(j,1,belong[n])
        fo(i,j*B+1,n)
            if (i%B!=1) g[i][j]+=g[i-1][j];
    fo(i,1,n){
        fo(j,1,belong[n]) g[i][j]+=g[i][j-1];
    }
    fo(j,1,belong[n]){
        fo(i,0,n) tree[i]=0;
        l=0;
        fo(i,(j-1)*B+1,min(j*B,n)){
            l+=query(a[i]+1);
            sum[i]=l;
            change(a[i]);
        }
        fo(i,0,n) tree[i]=0;
        l=0;
        fd(i,min(j*B,n),(j-1)*B+1){
            l+=query(n-a[i]+2);
            cnt[i]=l;
            change(n-a[i]+1);
        }
    }
    fo(i,1,n) b[i]=i;
    fo(i,1,belong[n]){
        l=(i-1)*B+1;r=min(i*B,n);
        sort(b+l,b+r+1,cmp);
    }
    fo(i,1,belong[n]) f[i][i]=sum[min(i*B,n)];
    fo(i,1,belong[n]-1)
        fo(j,i+1,belong[n]){
            top=0;
            fo(k,(i-1)*B+1,i*B) c[++top]=a[b[k]];
            tot=0;
            fo(k,(j-1)*B+1,min(j*B,n)) d[++tot]=a[b[k]];
            f[i][j]=work(top,tot);
        }
    fd(i,belong[n]-1,1)
        fo(j,i+1,belong[n])
            f[i][j]+=f[i][j-1]+f[i+1][j]-f[i+1][j-1];
    return ;
}

ll qry(int j,int k)
{
        l=belong[j];r=belong[k];
        if (l==r){
            ans=ask(l,j,k);
            return ans;
        }
        ans=f[l+1][r-1];
        /*ans+=ask(l,j,l*B);
        ans+=ask(r,(r-1)*B+1,k);*/
        ans+=cnt[j];
        ans+=sum[k];
        top=0;
        fo(i,(l-1)*B+1,l*B)
            if (b[i]>=j) c[++top]=a[b[i]];
        tot=0;
        fo(i,(r-1)*B+1,min(r*B,n))
            if (b[i]<=k) d[++tot]=a[b[i]];
        ans+=work(top,tot);
        /*fo(i,l+1,r-1) ans+=g[j][i];
        fo(i,l+1,r-1) ans+=g[k][i];*/
        ans+=g[j][r-1]-g[j][l];
        ans+=g[k][r-1]-g[k][l];
        return ans;
}

struct val {
    int l , r;
    ll v;
};
bool operator < (val x,val y)
{
    return x.r < y.r;
}
void solv()
{
    set<val> st;
    multiset<ll> vals;
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    init();
    ll z = qry(1 , n) ; cout << z <<' ' ;
    st.insert((val){1 , n , z}) ; vals.insert(z) ;
    //puts("ojbk") ; printf("Z %lld\n",z) ;
    for(int i = 1;i <= n;i++) {
        long long x ; cin >> x;
        x ^= z;
        auto it = st.lower_bound((val){x , x , 0}) ;
        int ul = it->l , ur = it->r;
        ll uv = it->v ;

        vals.erase(vals.find(uv)) ;
        st.erase(it) ;
        //printf("ul %d , ur %d\n",ul,ur) ;
        if(x - 1 >= ul) {
            ll nv = qry(ul , x - 1) ; //printf("Lnv %lld\n",nv);
            st.insert((val){ul , x - 1 , nv}) ; vals.insert(nv) ;
        }
        if(x + 1 <= ur) {
            ll nv = qry(x + 1 , ur); //printf("Rnv %lld\n",nv);
            st.insert((val){x + 1 , ur , nv}) ; vals.insert(nv) ;
        }


        z = 0;
        if(vals.size()) {
            auto it = vals.end() ; it-- ; z = (*it) ;
        }
        cout << z <<' ' ;
        //printf("Z %lld\n",z) ;
    }
    cout << '\n' ;
}
int main(){
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
   // freopen("in.txt","r",stdin) ;
    int t;cin >> t;
    while(t--) solv() ;
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7564kb

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:

7 0 0 0 0 0 
20 11 7 2 0 0 0 0 0 0 0 
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0 0 

result:

wrong answer 1st lines differ - expected: '7 0 0 0 0', found: '7 0 0 0 0 0 '