| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 488344 |
2021-11-18T16:39:56 Z |
madv809 |
Zamjene (COCI16_zamjene) |
C++14 |
|
4318 ms |
188428 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define LL long long
#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b - 1); ++i)
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define X first
#define Y second
#define pb push_back
#define ef else if
using namespace std;
const int mxn = 1e6 + 5;
const int mxk = 2e3 + 5;
const int INF = 1e9 + 7;
const LL base = 64319;
const LL MOD = 2928127154483;
int a[mxn], b[mxn], n, q;
LL Q[mxn], P[mxn], pow_base[mxn], deg[mxn], sz[mxn], global, ans4;
map<LL, LL> QP;
// deg[mxn], sz[mxn], global, luôn < = n
// riêng ans4 <= n^2 nên em nghĩ mấy cái này sẽ không tràn số được
// P[i] là mã hash của các số trên dãy ban đầu
// Q[i] là mã hash của các số trên dãy đã sort
//global là số lượng tập node mà có Q[i] != P[i]
//truy vấn 3 sẽ ra DA nếu global = 0 và ngược lại
// ans4 là đáp án cho truy vấn 4
// hợp 2 tập lại
int uni(const int &u, const int &v)
{
if (sz[u] > sz[v]) return uni(v, u);
sz[u] += sz[v];
sz[v] = u;
(P[u] += P[v])%=MOD;
(Q[u] += Q[v])%=MOD;
return u;
}
//tìm node đại diện của tập mà node u đang ở trong
int findd(const int &u)
{
if (sz[u] < 0) return u;
return (sz[u] = findd(sz[u]));
}
// update lại
inline void de(const int &i, const LL &val)
{
if (P[i] == Q[i]) return;
LL x = P[i] - Q[i];
global += val;
ans4 += -sz[i]*QP[(x + MOD)%MOD]*val;
QP[(MOD - x)%MOD] += -sz[i]*val;
}
int main()
{
//freopen("D:\\test.txt", "r", stdin);
//freopen("D:\\test2.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf("%d%d", &n, &q);
REP(i, 1, n)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int t = 0;
REP(i, 1, n)
{
if (b[i] != b[i - 1]) ++t;
deg[b[i]] = t;
}
pow_base[0] = 1;
REP(i, 1, n) pow_base[i] = base*pow_base[i - 1]%MOD;
// tính toán cho đáp án cho dãy ban đầu
REP(i, 1, n)
{
P[i] = pow_base[deg[a[i]]];
Q[i] = pow_base[deg[b[i]]];
if (P[i] != Q[i])
{
++global; LL x = P[i] - Q[i];
ans4 += QP[(x + MOD)%MOD];
++QP[(MOD - x)%MOD];
}
}
REP(i, 1, n) sz[i] = -1;
int u, v, x, y, par;
REP(i, 1, q)
{
scanf("%d", &t);
if (t <= 2)
{
scanf("%d%d", &u, &v);
if (t == 1)
{
x = findd(u); y = findd(v);
if (x == y) {swap(a[u], a[v]); continue;}
de(x, -1); de(y, -1);
P[x] -= pow_base[deg[a[u]]];
(P[x] += pow_base[deg[a[v]]] + MOD)%=MOD;
P[y] -= pow_base[deg[a[v]]];
(P[y] += pow_base[deg[a[u]]] + MOD)%=MOD;
de(x, 1); de(y, 1);
swap(a[u], a[v]);
}
else
{
x = findd(u); y = findd(v);
if (x == y) continue;
de(x, -1); de(y, -1);
par = uni(x, y);
de(par, 1);
}
}
ef (t == 3)
{
if (global == 0) printf("DA\n");
else printf("NE\n");
}
else printf("%lli\n", ans4);
}
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
zamjene.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
zamjene.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
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 |
328 KB |
Output is correct |
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
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 |
| # |
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 |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
5 ms |
976 KB |
Output is correct |
| 3 |
Correct |
9 ms |
936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
5684 KB |
Output is correct |
| 2 |
Correct |
88 ms |
7440 KB |
Output is correct |
| 3 |
Correct |
142 ms |
10524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1002 ms |
45648 KB |
Output is correct |
| 2 |
Correct |
3650 ms |
137344 KB |
Output is correct |
| 3 |
Correct |
4318 ms |
188428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1834 ms |
92744 KB |
Output is correct |
| 2 |
Correct |
3098 ms |
114676 KB |
Output is correct |
| 3 |
Correct |
1333 ms |
103584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
844 ms |
57940 KB |
Output is correct |
| 2 |
Correct |
2104 ms |
97676 KB |
Output is correct |
| 3 |
Correct |
1328 ms |
103488 KB |
Output is correct |
