oj.uz

Submission #234652

# Submission time Handle Problem Language Result Execution time Memory
234652 2020-05-25T02:16:38 Z mahmoudbadawy Zamjene (COCI16_zamjene) C++17
140 / 140
 5158 ms 188632 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=1e6+6,H=2,BASE=N;
const int MOD[H]={88199200,102345521};
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);
		if(hsh[x][0]||hsh[x][1]) mp[{hsh[x][0],hsh[x][1]}]-=sz[x];
		updAns(x,-1);
		updAns(y,-1);
		if(hsh[y][0]||hsh[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;
		if(hsh[y][0]||hsh[y][1]) mp[{hsh[y][0],hsh[y][1]}]+=sz[y];
		updAns(y,1);
	}
	void mod(int x,int y,int z)
	{
		x=(*this)(x);
		if(hsh[x][0]||hsh[x][1]) mp[{hsh[x][0],hsh[x][1]}]-=sz[x];
		updAns(x,-1);
		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);
		if(hsh[x][0]||hsh[x][1]) mp[{hsh[x][0],hsh[x][1]}]+=sz[x];
	}
} dsu;

void print()
{
	return;
	cout << "ARR: ";
	for(int i=0;i<4;i++)
		cout << arr[i] << " ";
	cout << endl;
	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--;
			int ox=x,oy=y;
			swap(arr[x],arr[y]);
			x=dsu(x); y=dsu(y);
			if(x==y) continue;
			dsu.mod(x,arr[ox],arr[oy]);
			dsu.mod(y,arr[oy],arr[ox]);
		}
		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:99: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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~
zamjene.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
zamjene.cpp:119: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:126:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 16 ms 8192 KB Output is correct
3 Correct 16 ms 8192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 16 ms 8192 KB Output is correct
3 Correct 17 ms 8192 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 17 ms 8192 KB Output is correct
3 Correct 16 ms 8192 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8192 KB Output is correct
2 Correct 17 ms 8320 KB Output is correct
3 Correct 17 ms 8320 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8192 KB Output is correct
2 Correct 18 ms 8192 KB Output is correct
3 Correct 17 ms 8296 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8576 KB Output is correct
2 Correct 24 ms 8832 KB Output is correct
3 Correct 23 ms 8576 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11000 KB Output is correct
2 Correct 131 ms 13796 KB Output is correct
3 Correct 206 ms 16920 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 36216 KB Output is correct
2 Correct 4457 ms 137324 KB Output is correct
3 Correct 5158 ms 188632 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2415 ms 73464 KB Output is correct
2 Correct 3932 ms 107000 KB Output is correct
3 Correct 1826 ms 95764 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 39544 KB Output is correct
2 Correct 2722 ms 90044 KB Output is correct
3 Correct 1795 ms 95864 KB Output is correct