| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 209132 |
2020-03-13T09:04:20 Z |
Sensei |
Zamjene (COCI16_zamjene) |
C++14 |
|
1489 ms |
73576 KB |
/*
DATE: 2020-03-13 10:51:02
NAME:
PROBLEM: COCI16_ZAMJENE
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
const long long MOD = 1e16 + 7;
const int prime = 1234577;
long long add(long long x, long long y) {
return ((x % MOD) + (y % MOD)) % MOD;
}
long long sub(long long x, long long y) {
return ((x % MOD) + MOD - (y % MOD)) % MOD;
}
long long mul(long long x, long long y) {
return ((x % MOD) * (y % MOD)) % MOD;
}
long long liftt[MAXN + 7];
long long lift(int x) {
return liftt[x];
}
int p[MAXN + 7];
int q[MAXN + 7];
int par[MAXN + 7];
int r[MAXN + 7];
long long P[MAXN + 7];
long long Q[MAXN + 7];
unordered_map<long long, int> cnt;
long long ans_for_4 = 0;
void ins(int x, int y) {
// cerr << "ins: " << x << " " << y << " " << p[y] << "\n";
long long t = sub(P[x], Q[x]);
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[t] -= r[x];
P[x] = add(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[t] += r[x];
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
}
void del(int x, int y) {
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[t] -= r[x];
P[x] = sub(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[t] += r[x];
}
void makeset(int x) {
par[x] = x;
r[x] = 1;
Q[x] = lift(q[x]);
P[x] = 0;
cnt[sub(P[x], Q[x])] += r[x];
ins(x, x);
}
int findset(int x) {
if (par[x] != x) {
par[x] = findset(par[x]);
}
return par[x];
}
void link(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return;
}
if (r[x] > r[y]) {
par[y] = x;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] -= r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] -= r[y];
P[x] = add(P[x], P[y]);
Q[x] = add(Q[x], Q[y]);
r[x] += r[y];
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] += r[x];
}
else {
par[x] = y;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] -= r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] -= r[y];
P[y] = add(P[y], P[x]);
Q[y] = add(Q[y], Q[x]);
r[y] += r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 += r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] += r[y];
}
}
int main() {
liftt[0] = 1;
for (int i = 1; i <= MAXN; i++) {
liftt[i] = mul(liftt[i - 1], prime);
}
int n, qry;
cin >> n >> qry;
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
q[i] = p[i];
}
sort(q + 1, q + n + 1);
for (int i = 1; i <= n; i++) {
makeset(i);
}
int ccnt = n;
while (qry--) {
// for (unordered_map<long long, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
// cerr << it->first << " " << it->second << "\n";
// }
int ty;
scanf("%d", &ty);
if (ty == 1) {
int a, b;
scanf("%d %d", &a, &b);
int x = findset(a);
int y = findset(b);
if (x == y) {
continue;
}
del(x, a);
ins(x, b);
del(y, b);
ins(y, a);
swap(p[a], p[b]);
}
else if (ty == 2) {
int a, b;
scanf("%d %d", &a, &b);
if (findset(a) != findset(b)) {
ccnt--;
}
link(a, b);
}
else if (ty == 3) {
if (cnt[0] == n) {
printf("DA\n");
}
else {
printf("NE\n");
}
}
else if (ty == 4) {
printf("%lld\n", ans_for_4);
}
}
return 0;
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
zamjene.cpp:182:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ty);
~~~~~^~~~~~~~~~~
zamjene.cpp:185:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:200:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
8184 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
8316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
11768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1078 ms |
40708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1489 ms |
73576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1076 ms |
46984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
