QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557563 | #5425. Proposition Composition | Wuyanru | WA | 222ms | 26308kb | C++14 | 4.1kb | 2024-09-11 10:16:57 | 2024-09-11 10:16:58 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int mi[1000001];
int ma[1000001];
int bel[250005];//每一个点对应的链表编号
int root[250005];//链表的链头
int cnt[250005];//链表内元素个数
int nx[250005];
int lt[200005];
set<int>S0,S1;
int n,m,c;
ll ans;
inline void push_up(int p)
{
mi[p]=min(mi[p*2],mi[p*2|1]);
ma[p]=max(ma[p*2],ma[p*2|1]);
}
void update(int p,int pl,int pr,int x)
{
if(pl==pr)
{
mi[p]=lt[pl],ma[p]=nx[pl];
return ;
}
int mid=(pl+pr)>>1;
if(x<=mid) update(p*2,pl,mid,x);
else update(p*2|1,mid+1,pr,x);
push_up(p);
}
void find(int p,int pl,int pr,int l,int r,vc<pi>&v)
{
if(mi[p]>l&&ma[p]<r) return ;
if(pl==pr)
{
if(mi[p]<l) v.push_back(pi(bel[pl],pl));
if(ma[p]>r) v.push_back(pi(bel[pl],nx[pl]));
return ;
}
int mid=(pl+pr)>>1;
if(l<=mid) find(p*2,pl,mid,l,r,v);
if(mid<r) find(p*2|1,mid+1,pr,l,r,v);
}
inline void cover(int l,int r)
{
auto it=S1.lower_bound(l);
while(it!=S1.end()&&*it<r) S1.erase(it),it=S1.lower_bound(l);
it=S0.lower_bound(l);
while(it!=S0.end()&&*it<r) S1.insert(*it),S0.erase(it),it=S0.lower_bound(l);
}
inline ll C(int c){ return (ll)c*(c-1)/2;}
inline void run(int L,int P1,int P2)
{
ans-=C(cnt[L]);
vc<int>v[2];int i=root[L],j=P1,f=-1;//哪个小
while(true)
{
v[0].push_back(i),v[1].push_back(j);
if(nx[i]==i){ f=0;break;}
else if(nx[j]==P2){ f=1;break;}
i=nx[i]==P1?P2:nx[i],j=nx[j];
}
int N1=lt[P1],N2=lt[P2];
lt[P1]=P1,nx[N2]=N2;nx[N1]=P2,lt[P2]=N1;
update(1,1,n,P1),update(1,1,n,P2);
update(1,1,n,N1),update(1,1,n,N2);
c++;cnt[c]=0;
root[c]=v[f].front();
for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
ans+=C(cnt[L])+C(cnt[c]);
root[L]=v[1-f].front();
}
inline void run(int L,int P)
{
ans-=C(cnt[L]);
vc<int>v[2];int i=root[L],j=P,f=-1;
while(true)
{
v[0].push_back(i),v[1].push_back(j);
if(nx[i]==P){ f=0;break;}
else if(nx[j]==j){ f=1;break;}
i=nx[i],j=nx[j];
}
int N=lt[P];
nx[N]=N,lt[P]=P;
update(1,1,n,N),update(1,1,n,P);
c++;cnt[c]=0;
root[c]=v[f].front();
for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
ans+=C(cnt[L])+C(cnt[c]);
root[L]=v[1-f].front();
}
inline void run()
{
int l=read(),r=read();
if(l>r) swap(l,r);
if(l==r) return ;
vc<pi>v;find(1,1,n,l,r-1,v);cover(l,r);
sort(v.begin(),v.end());
// for(auto i:v) printf("(%d,%d)\n",i.first,i.second);
for(unsigned i=0;i<v.size();i++)
{
if(i+1<v.size()&&v[i].first==v[i+1].first)
{
run(v[i].first,v[i].second,v[i+1].second);
i++;
}
else run(v[i].first,v[i].second);
}
}
inline void output()
{
return ;
printf("output ans=%lld %d %d\n",ans,(int)S0.size(),(int)S1.size());
printf("S0 : ");for(int i:S0) printf("%d ",i);;putchar('\n');
printf("S1 : ");for(int i:S1) printf("%d ",i);;putchar('\n');
for(int i=1;i<n;i++) printf("i=%d : bel=%d lt=%d nx=%d\n",i,bel[i],lt[i],nx[i]);
for(int i=1;i<=c;i++) printf("%d : cnt=%d root=%d\n",i,cnt[i],root[i]);
}
inline void solve()
{
S0.clear(),S1.clear();
n=read(),m=read(),c=0;
if(n==1)
{
for(int i=1;i<=m;i++)
{
assert(read()==1&&read()==1);
printf("0\n");
}
return ;
}
c=1;cnt[1]=n-1,root[1]=1,ans=C(n-1);
for(int i=1;i<n;i++)
{
nx[i]=min(n-1,i+1);
lt[i]=max(1,i-1);
bel[i]=1;
update(1,1,n,i);
S0.insert(i);
}
output();
for(int i=1;i<=m;i++)
{
run();
ll o=ans+(ll)S0.size()*(n-1-S0.size()+i)+S1.size();
printf("%lld\n",o);output();
}
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
/*
1
7 4
2 6
3 5
1 6
4 7
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9896kb
input:
3 4 3 2 4 4 2 3 3 7 3 3 4 1 2 1 7 6 4 1 3 4 6 2 5 3 4
output:
6 5 6 21 24 10 15 12 3 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 45ms
memory: 10184kb
input:
45540 10 9 10 1 1 10 10 1 1 10 1 10 10 1 1 10 3 3 10 1 10 4 1 2 1 10 3 4 1 10 7 6 7 1 5 6 1 7 6 6 7 1 6 7 9 7 3 3 7 7 5 4 1 1 9 1 9 1 6 5 8 7 1 8 4 4 5 6 1 1 1 8 6 6 4 5 3 3 3 2 3 1 3 3 3 9 3 1 3 3 2 2 3 3 3 1 2 2 1 1 2 3 3 1 10 1 2 1 7 1 1 7 3 8 1 3 1 3 3 3 1 3 2 2 1 3 1 3 3 3 3 6 3 1 1 3 1 3 1 3 1...
output:
45 36 36 36 36 36 36 36 36 45 36 28 21 21 15 10 10 10 6 36 44 50 57 28 21 15 28 28 21 21 15 15 10 3 1 1 3 3 3 3 1 1 1 0 0 45 21 3 1 1 1 1 1 1 1 3 1 1 1 1 1 45 36 36 36 36 36 36 36 3 3 1 0 0 0 0 0 0 3 1 0 0 15 10 10 0 0 0 0 0 0 0 0 28 34 21 6 6 6 6 1 0 0 21 15 15 0 0 0 0 0 0 0 45 53 0 0 0 0 0 0 0 0 1...
result:
ok 249586 numbers
Test #3:
score: 0
Accepted
time: 86ms
memory: 12236kb
input:
2507 86 4 41 41 36 36 31 30 86 1 110 22 1 110 110 1 11 11 110 1 110 1 110 1 1 110 107 106 72 72 106 106 74 74 1 110 110 1 58 58 110 1 110 1 1 110 101 100 110 1 100 100 110 1 8 7 114 180 114 1 114 1 114 1 1 114 1 114 114 1 37 38 49 48 105 106 1 114 90 90 1 114 9 9 114 1 67 68 20 20 114 1 1 114 54 55 ...
output:
3655 3740 3823 3570 5995 5886 5886 5886 5886 5886 5886 5778 5778 5778 5778 5778 5778 5778 5778 5778 5778 5671 5671 5671 5671 5565 6441 6328 6328 6328 6328 6328 6216 6105 5995 5995 5995 5995 5995 5995 5886 5886 5886 5886 5778 5671 5671 5565 5565 5460 5460 5460 5460 5460 5356 5253 5253 5253 5151 5151 ...
result:
ok 249877 numbers
Test #4:
score: 0
Accepted
time: 143ms
memory: 14972kb
input:
3 82425 27858 30801 30802 1 82425 73850 73850 1 82425 65949 65949 82425 1 76026 76025 61936 61936 82425 1 82425 1 82425 1 6504 6504 82425 1 25155 25156 79743 79743 1 82425 69406 69406 29247 29247 18351 18351 23171 23170 29704 29703 82425 1 1 82425 82425 1 74918 74917 22395 22394 893 894 82425 1 391 ...
output:
3396899100 3396816676 3396816676 3396734253 3396734253 3396734253 3396651831 3396651831 3396651831 3396651831 3396651831 3396651831 3396651831 3396569410 3396569410 3396569410 3396569410 3396569410 3396569410 3396486990 3396404571 3396404571 3396404571 3396404571 3396322153 3396239736 3396157320 339...
result:
ok 116748 numbers
Test #5:
score: -100
Wrong Answer
time: 222ms
memory: 26308kb
input:
1 250000 250000 248617 248617 1 250000 47808 47809 1 250000 1 250000 110493 110494 1 250000 66675 66676 141326 141327 250000 1 115279 115280 193218 193219 250000 1 77714 77715 1 250000 1 250000 212943 212943 223061 223060 1 250000 250000 1 1 250000 71059 71059 1 250000 246523 246522 1 250000 88700 8...
output:
31249875000 31249875000 31249625001 31249375003 31249375003 31249125006 31249125006 31248875010 31248625015 31248625015 31248375021 31248125028 31248125028 31247875036 31247875036 31247875036 31247875036 31247625045 31247625045 31247625045 31247625045 31247625045 31247625045 31247375055 31247375055 ...
result:
wrong answer 4475th numbers differ - expected: '30971000521', found: '30932945137'