QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #167098 | #7108. Couleur | FishAndCat | RE | 2ms | 9876kb | C++14 | 10.3kb | 2023-09-07 03:08:16 | 2023-09-07 03:08:17 |
Judging History
answer
#include <bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const long long maxn=100000+10,B=318;
long long 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];
long long sum[maxn],cnt[maxn];
long long i,j,k,l,r,s,t,n,m,tot,top,now,_;
long long ans;
map<long long,int>mp;
set<int>st;
int lowbit(int x){return x&(-x);}
long long read(){
long long x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
bool cmp(int x,int y){
return a[x]<a[y];
}
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;
}
long long work(long long top,long long tot){
long long 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;
}
long long ask(int x,int l,int r){
int i;
long long 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;
}
long long Query(int j,int k) {
l=belong[j];r=belong[k];
if (l==r){
ans=ask(l,j,k);
return ans;
}
cout<<j<<" "<<k<<"-"<<l<<" "<<r<<"\n";
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;
}
int main(){
_=read();
while(_--)
{
n=read();
fo(i,1,n) a[i]=read(),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];
long long p=0;
long long re=Query(1,n);
mp.clear();st.clear();
mp[ans]++;
mp[0]++;
st.insert(0);st.insert(n+1);
memset(tree,0,sizeof(int)*(n+5));
for(int i=1;i<=n;i++){
p=read();
int u=p^re;
int L,R;
auto it=st.lower_bound(u);
R=(*it)-1;
it--;
L=(*it)+1;
st.insert(u);
// int l=1,r=u;
// while(l<r)
// {
// int mid=l+r>>1;
// if(query(mid)>query(u))l=mid+1;
// else r=mid;
// }
// L=l;
// l=u,r=n+1;
// while(l<r)
// {
// int mid=l+r+1>>1;
// if(query(mid)<query(u))r=mid-1;
// else l=mid;
// }
// R=l-1; //找到了一个划分过了的L到R均可用的区间 为什么这样做是假的做法啊。曹了的
if(i==n)printf("%lld\n",re);
else printf("%lld ",re);
mp[Query(L,R)]--;
if(mp[Query(L,R)]==0)mp.erase(Query(L,R));
if(u+1<=R)
mp[Query(u+1,R)]++;
if(u-1>=L)
mp[Query(L,u-1)]++;
re=prev(mp.end())->first;
}
}
} //从来没见过这么恶心人的事情 真丝麻啊
//RE 又是RE 我RE私你的吗
// #include <bits/stdc++.h>
// using namespace std;
// long long a[30000000];
// // map<long long,int>mp;
// int main()
// {
// // for(int i=1;i<=1000000;i++)
// // mp[i]=1;
// return 0;
// }
// 就是方法假了 否则不会RE
// 为什么这样是假的做法 我真的不懂了。
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？ 为什么？
// RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?
// RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?
// RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?RE?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9876kb
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 20 11 7 2 0 0 0 0 0 0 42 31 21 14 14 4 1 1 1 0 0 0 0 0 0
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
11116 10 10 5 10 3 6 4 8 5 9 8 31 27 24 11 12 3 0 2 3 1 10 8 2 7 2 8 10 1 10 9 10 6 5 2 13 2 1 0 1 3 1 10 7 10 7 6 1 3 10 6 7 9 21 18 10 1 6 5 4 8 9 10 10 2 10 4 8 8 5 7 2 6 7 20 10 9 1 15 0 4 2 9 7 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 6 3 5 2 7 10 9 1 4 8 10 1 10 1 3...
output:
21 18 16 12 10 6 4 1 1 0 12 12 10 10 4 4 4 2 1 0 20 16 9 5 3 3 3 0 0 0 22 14 8 8 5 5 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 12 7 4 4 2 2 1 0 0 20 18 8 3 1 1 0 0 0 0 45 21 21 10 3 3 3 0 0 0 17 11 8 2 1 1 1 0 0 0 13 4 1 0 0 0 0 0 0 0 29 27 22 15 9 7 4 3 1 0 26 16 9 2 1 1 1 1 1 0 0 0 0 0 0 ...