#include <bits/stdc++.h>
using namespace std;
const int N=1e6+6,H=2,BASE=N;
const int MOD[H]={(int)1e9+7,(int)1e9+9};
int pw[N][H];
map< pair<int,int>, int > mp;
long long ans4,bad;
int arr[N],sor[N];
inline int neg(int x,int i)
{
x=MOD[i]-x;
if(x>=MOD[i]) return x-MOD[i];
return x;
}
struct DSU{
int pa[N],sz[N];
int hsh[N][H]; void init(int n)
{
iota(pa,pa+n,0);
fill(sz,sz+n,1);
}
int operator() (int x)
{
if(pa[x]==x) return x;
return pa[x]=(*this)(pa[x]);
}
void updAns(int x,int p)
{
if(hsh[x][0]||hsh[x][1]) {bad+=p; ans4+=1LL*p*mp[{neg(hsh[x][0],0),neg(hsh[x][1],1)}]*sz[x];}
}
void operator() (int x,int y)
{
x=(*this)(x); y=(*this)(y);
if(x==y) return;
if(sz[x]>sz[y]) swap(x,y);
mp[{hsh[x][0],hsh[x][1]}]-=sz[x];
updAns(x,-1);
updAns(y,-1);
mp[{hsh[y][0],hsh[y][1]}]-=sz[y];
for(int i=0;i<H;i++)
{
hsh[y][i]+=hsh[x][i];
hsh[y][i]%=MOD[i];
hsh[y][i]+=MOD[i];
while(hsh[y][i]>=MOD[i]) hsh[y][i]-=MOD[i];
}
pa[x]=y; sz[y]+=sz[x]; sz[x]=0;
mp[{hsh[y][0],hsh[y][1]}]+=sz[y];
updAns(y,1);
}
void mod(int x,int y,int z)
{
x=(*this)(x);
updAns(x,-1);
mp[{hsh[x][0],hsh[x][1]}]-=sz[x];
for(int i=0;i<H;i++)
{
hsh[x][i]+=pw[y][i];
hsh[x][i]-=pw[z][i];
hsh[x][i]%=MOD[i];
hsh[x][i]+=MOD[i];
while(hsh[x][i]>=MOD[i]) hsh[x][i]-=MOD[i];
}
updAns(x,1);
mp[{hsh[x][0],hsh[x][1]}]+=sz[x];
}
} dsu;
void print()
{
return;
cout << "DATA: " << endl;
for(int i=0;i<4;i++)
{
cout << dsu(i) << endl;
cout << dsu.hsh[i][0] << " " << dsu.hsh[i][1] << endl;
cout << dsu.sz[i] << " " << mp[{neg(dsu.hsh[i][0],0),neg(dsu.hsh[i][1],1)}] << endl;
}
}
int main()
{
pw[0][0]=pw[0][1]=1;
for(int i=1;i<N;i++)
{
for(int j=0;j<H;j++)
pw[i][j]=(1LL*BASE*pw[i-1][j])%MOD[j];
}
int n,q;
scanf("%d %d",&n,&q);
dsu.init(n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
sor[i]=arr[i];
}
sort(sor,sor+n);
for(int i=0;i<n;i++)
{
dsu.mod(i,arr[i],sor[i]);
}
while(q--)
{
print();
int t;
scanf("%d",&t);
if(t==2)
{
int x,y;
scanf("%d %d",&x,&y);
x--; y--;
dsu(x,y);
}
else if(t==1)
{
int x,y;
scanf("%d %d",&x,&y);
x--; y--;
swap(arr[x],arr[y]);
x=dsu(x); y=dsu(y);
if(x==y) continue;
dsu.mod(x,arr[x],arr[y]);
dsu.mod(y,arr[y],arr[x]);
}
else if(t==3)
{
//cout << bad << endl;
printf("%s\n",(bad==0?"DA":"NE"));
}
else
{
printf("%lld\n",ans4);
}
}
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[i]);
~~~~~^~~~~~~~~~~~~~
zamjene.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
zamjene.cpp:115:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
8312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
8576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
11000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1489 ms |
40872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2441 ms |
78592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1257 ms |
40568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
