QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#167720 | #7108. Couleur | Delay_for_five_minutes | WA | 2ms | 7564kb | C++14 | 5.2kb | 2023-09-07 16:50:17 | 2023-09-07 16:50:18 |
Judging History
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 '