oj.uz

Submission #532473

# Submission time Handle Problem Language Result Execution time Memory
532473 2022-03-03T01:49:05 Z colazcy Zamjene (COCI16_zamjene) C++17
140 / 140
 4178 ms 180628 KB 
#include <cstdio>
#include <cassert>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using ull = unsigned long long;
constexpr int maxn = 1e6 + 10;
	
ull trans[maxn];
int n,q,now[maxn],target[maxn];
std::mt19937_64 eng(743);
namespace dsu{
	int f[maxn],sz[maxn];
	void init(){
		rep(i,1,n)f[i] = i,sz[i] = 1;
	}
	int find(const int x){return x == f[x] ? x : f[x] = find(f[x]);}
};
std::map<ull,int> mp;
ll ans;
ull sum[maxn];
void ins(const ull s,const int sz){
	if(s != 0)ans += 1ll * sz * mp[-s];
	mp[s] += sz;
}
void del(const ull s,const int sz){
	mp[s] -= sz;
	if(s != 0)ans -= 1ll * sz * mp[-s];
}
void init(){
	rep(i,1,n)target[i] = now[i];
	std::sort(target + 1,target + 1 + n);
	rep(i,1,n)trans[now[i]] = eng();
	dsu::init();
	rep(i,1,n)
		sum[i] = trans[now[i]] - trans[target[i]];
	rep(i,1,n)ins(sum[i],1);
}

void modify_swap(const int a,const int b){
	let x = dsu::find(a),y = dsu::find(b);
	if(x == y){
		std::swap(now[a],now[b]);
		return;
	}
	del(sum[x],dsu::sz[x]);
	del(sum[y],dsu::sz[y]);
	sum[x] -= trans[now[a]];
	sum[y] -= trans[now[b]];
	std::swap(now[a],now[b]);
	sum[x] += trans[now[a]];
	sum[y] += trans[now[b]];
	ins(sum[x],dsu::sz[x]);
	ins(sum[y],dsu::sz[y]);
}
void modify_merge(const int a,const int b){
	let x = dsu::find(a),y = dsu::find(b);
	if(x == y)return;
	del(sum[x],dsu::sz[x]);
	del(sum[y],dsu::sz[y]);
	sum[y] += sum[x];
	dsu::sz[y] += dsu::sz[x];
	dsu::f[x] = y;
	ins(sum[y],dsu::sz[y]);
}
bool query_sort(){
	return mp[0] == n;
}
ll query_count(){
	return ans;
}
int main(){
	// std::freopen("zamjene.in","r",stdin);
	// std::freopen("zamjene.out","w",stdout);
	std::scanf("%d %d",&n,&q);
	rep(i,1,n)std::scanf("%d",now + i);
	init();
	repn(q){
		int opt,x,y; std::scanf("%d",&opt);
		if(opt == 1){
			std::scanf("%d %d",&x,&y);
			modify_swap(x,y);
		}else if(opt == 2){
			std::scanf("%d %d",&x,&y);
			modify_merge(x,y);
		}else if(opt == 3)std::puts(query_sort() ? "DA" : "NE");
		else if(opt == 4)std::printf("%lld\n",query_count());
	}	
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:85:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  std::scanf("%d %d",&n,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  rep(i,1,n)std::scanf("%d",now + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
zamjene.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   int opt,x,y; std::scanf("%d",&opt);
      |                ~~~~~~~~~~^~~~~~~~~~~
zamjene.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 704 KB Output is correct
2 Correct 6 ms 720 KB Output is correct
3 Correct 6 ms 720 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4036 KB Output is correct
2 Correct 79 ms 5836 KB Output is correct
3 Correct 142 ms 9176 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 37684 KB Output is correct
2 Correct 3524 ms 129300 KB Output is correct
3 Correct 4178 ms 180628 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1976 ms 76944 KB Output is correct
2 Correct 3281 ms 98976 KB Output is correct
3 Correct 1532 ms 87752 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 42076 KB Output is correct
2 Correct 2263 ms 82172 KB Output is correct
3 Correct 1496 ms 87736 KB Output is correct