| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 165653 |
2019-11-28T04:31:42 Z |
_qVp_ |
Zamjene (COCI16_zamjene) |
C++14 |
|
5688 ms |
182784 KB |
#include <bits/stdc++.h>
using namespace std;
const int base = 1234577;
const int md = 1e6 + 10;
int n, T;
int p[md], q[md], sz[md], lab[md];
long long pw[md], id[md], val[md];
long long pairs;
map < long long, int > diff_nodes;
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
//neg = (c == '-') ? -1 : 1;
*x = c - '0';
//readchar();
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c - '0';
//*x *= neg;
return 1;
}
void print(long long n) {
//cout << n << endl;
if (!n) return ;
print(n / 10);
putchar(n % 10 + 48);
}
void addNode(int sign, long long diff, int num) {
if (diff != 0)
pairs += sign * num * diff_nodes[-diff];
diff_nodes[diff] += sign * num;
}
int root(int x) {
if (lab[x] < 0)
return x;
return lab[x] = root(lab[x]);
}
void init() {
ReadInt(&n); ReadInt(&T);
//cerr << n << " " << T << endl;
pw[0] = 1;
for(int i = 1; i < md; i++)
pw[i] = pw[i - 1] * base;
for(int i = 1; i <= n; i++) {
ReadInt(&p[i]);
// cerr << p[i] << endl;
q[i] = p[i];
lab[i] = -1;
sz[i] = 1;
}
sort(q + 1, q + 1 + n);
for(int i = 1; i <= n; i++) {
id[i] = pw[q[i]];
val[i] = pw[p[i]];
addNode(1, id[i] - val[i], sz[i]);
}
}
void add(int sign, int ru, int u, int v) {
id[ru] += sign * pw[u];
val[ru] += sign * pw[v];
sz[ru] += sign;
}
void merges(int u, int v) {
//cerr << "checking";
int ru = root(u), rv = root(v);
if (ru == rv)
return ;
if (lab[ru] > lab[rv])
swap(ru, rv);
addNode(-1, id[ru] - val[ru], sz[ru]);
addNode(-1, id[rv] - val[rv], sz[rv]);
lab[ru] += lab[rv];
lab[rv] = ru;
sz[ru] += sz[rv];
id[ru] += id[rv];
val[ru] += val[rv];
//cout << id[ru] << " " << val[ru] << endl;
addNode(1, id[ru] - val[ru], sz[ru]);
}
int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios_base::sync_with_stdio(0);
init();
while (T--) {
int type;
ReadInt(&type);
//cerr << "*" << type << endl;
if (type == 1) {
int u, v;
ReadInt(&u); ReadInt(&v);
// cerr << u << " " << v << endl;
int ru = root(u), rv = root(v);
if (ru == rv) {
swap(p[u], p[v]);
continue;
}
//cerr << i << endl;
addNode(-1, id[ru] - val[ru], sz[ru]);
addNode(-1, id[rv] - val[rv], sz[rv]);
add(-1, ru, u, p[u]);
add(-1, rv, v, p[v]);
swap(p[u], p[v]);
add(1, ru, u, p[u]);
add(1, rv, v, p[v]);
addNode(1, id[ru] - val[ru], sz[ru]);
addNode(1, id[rv] - val[rv], sz[rv]);
} else if (type == 2) {
int u, v;
ReadInt(&u); ReadInt(&v);
// cerr << u <<" " << v << endl;
merges(u, v);
} else if (type == 3) {
if (diff_nodes[0] == n)
puts("DA");
else puts("NE");
} else {
if (pairs == 0)
puts("0");
else {
print(pairs); puts("");
}
}
}
return 0;
}
Compilation message
zamjene.cpp: In function 'int ReadInt(int*)':
zamjene.cpp:25:20: warning: unused variable 'neg' [-Wunused-variable]
static char c, neg;
^~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:135:16: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
} else if (type == 3) {
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8316 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8312 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8312 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8312 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
9 ms |
8312 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
8696 KB |
Output is correct |
| 2 |
Correct |
13 ms |
8824 KB |
Output is correct |
| 3 |
Correct |
15 ms |
8828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
12792 KB |
Output is correct |
| 2 |
Correct |
96 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
168 ms |
17628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1190 ms |
41140 KB |
Output is correct |
| 2 |
Correct |
5112 ms |
131796 KB |
Output is correct |
| 3 |
Correct |
5688 ms |
182784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2487 ms |
82348 KB |
Output is correct |
| 2 |
Correct |
4279 ms |
103432 KB |
Output is correct |
| 3 |
Correct |
1737 ms |
91088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
884 ms |
48176 KB |
Output is correct |
| 2 |
Correct |
2904 ms |
87444 KB |
Output is correct |
| 3 |
Correct |
1786 ms |
91000 KB |
Output is correct |
