제출 #96784

#제출 시각아이디문제언어결과실행 시간메모리
96784tieunhiZamjene (COCI16_zamjene)C++14
0 / 140
6092 ms67028 KiB
#include <bits/stdc++.h> #define FOR(i, u, v) for (int i = u; i <= v; i++) #define FORD(i, v, u) for (int i = v; i >= u; i--) #define ll long long #define pill pair<int, ll> #define PB push_back #define mp make_pair #define F first #define S second #define N 1000005 #define BASE 107 #define maxc 1000000007 #define mid (r + l)/2 using namespace std; int n, numQ, a[N], b[N], sz[N], numCC, cc, root[N]; ll val[2][N], ansType4, base[N]; map<ll, int> ma; int readInt () { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result*10 + (ch - '0'); } if (minus) return -result; else return result; } void setup() { n = readInt(); numQ = readInt(); cc = n; FOR(i, 1, n) a[i] = readInt(), b[i] = a[i]; } void subcc(int u) { ll Val = val[0][u] - val[1][u]; if (Val == 0) { numCC--; return; } ansType4 -= 1ll*sz[u]*ma[-Val]; ma[Val] -= sz[u]; } void addcc(int u) { ll Val = val[0][u] - val[1][u]; if (Val == 0) { numCC++; return; } ansType4 += 1ll*sz[u]*ma[-Val]; ma[Val] += sz[u]; } void prepare() { sort(b+1, b+n+1); base[0] = 1; FOR(i, 1, N-1) base[i] = base[i-1]*BASE; FOR(i, 1, n) { sz[i] = 1; val[0][i] = base[a[i]]; val[1][i] = base[b[i]]; addcc(i); } } int get_root(int u) { return (root[u] == 0) ? u : root[u] = get_root(root[u]); } void inline add(ll &A, ll B) {A += B;} void inline sub(ll &A, ll B) {A -= B;} int main() { ios_base::sync_with_stdio(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); //freopen("OUT.TXT", "w", stdout); setup(); prepare(); while (numQ--) { int type, u, v; type = readInt(); if (type <= 2) u = readInt(); v = readInt(); if (type == 1) { int p = get_root(u); int q = get_root(v); if (p == q) continue; subcc(p); subcc(q); add(val[0][p], base[a[v]]); add(val[0][q], base[a[u]]); sub(val[0][p], base[a[u]]); sub(val[0][q], base[a[v]]); swap(a[u], a[v]); addcc(p); addcc(q); } else if (type == 2) { int p = get_root(u); int q = get_root(v); if (p == q) continue; subcc(p); subcc(q); root[q] = p; sz[p] += sz[q]; add(val[0][p], val[0][q]); add(val[1][p], val[1][q]); cc--; addcc(p); } else if (type == 3) { if (cc == numCC) cout <<"DA\n"; else cout <<"NE\n"; } else cout <<ansType4<<'\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

zamjene.cpp: In function 'int main()':
zamjene.cpp:101:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if (type <= 2) u = readInt(); v = readInt();
         ^~
zamjene.cpp:101:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if (type <= 2) u = readInt(); v = readInt();
                                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...