Submission #209141

#TimeUsernameProblemLanguageResultExecution timeMemory
209141SenseiZamjene (COCI16_zamjene)C++14
70 / 140
6112 ms215544 KiB
/* 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 + 3; const int prime = 331; const int prime2 = 67; 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 liftt2[MAXN + 7]; long long lift(int x) { return liftt[x]; } long long lift2(int x) { return liftt2[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]; long long P2[MAXN + 7]; long long Q2[MAXN + 7]; map<pair<long long, 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]); long long t2 = sub(P2[x], Q2[x]); // cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n"; if (t != 0 or t2 != 0) { ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{t, t2}] -= r[x]; P[x] = add(P[x], lift(p[y])); P2[x] = add(P2[x], lift2(p[y])); t = sub(P[x], Q[x]); t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{t, t2}] += 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]); long long t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{t, t2}] -= r[x]; P[x] = sub(P[x], lift(p[y])); P2[x] = sub(P2[x], lift2(p[y])); t = sub(P[x], Q[x]); t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{t, t2}] += r[x]; } void makeset(int x) { par[x] = x; r[x] = 1; Q[x] = lift(q[x]); Q2[x] = lift2(q[x]); P[x] = 0; P2[x] = 0; cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[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]); long long t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] -= r[x]; t = sub(P[y], Q[y]); t2 = sub(P2[y], Q2[y]); if (t != 0 or t2 != 0) { ans_for_4 -= r[y] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] -= r[y]; P[x] = add(P[x], P[y]); P2[x] = add(P2[x], P2[y]); Q[x] = add(Q[x], Q[y]); Q2[x] = add(Q2[x], Q2[y]); r[x] += r[y]; t = sub(P[x], Q[x]); t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 += r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] += r[x]; } else { par[x] = y; long long t = sub(P[x], Q[x]); long long t2 = sub(P2[x], Q2[x]); if (t != 0 or t2 != 0) { ans_for_4 -= r[x] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[x], Q[x]), sub(P2[x], Q2[x])}] -= r[x]; t = sub(P[y], Q[y]); t2 = sub(P2[y], Q2[y]); if (t != 0 or t2 != 0) { ans_for_4 -= r[y] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] -= r[y]; P[y] = add(P[y], P[x]); P2[y] = add(P2[y], P2[x]); Q[y] = add(Q[y], Q[x]); Q2[y] = add(Q2[y], Q2[x]); r[y] += r[x]; t = sub(P[y], Q[y]); t2 = sub(P2[y], Q2[y]); if (t != 0 or t2 != 0) { ans_for_4 += r[y] * cnt[{sub(0, t), sub(0, t2)}]; } cnt[{sub(P[y], Q[y]), sub(P2[y], Q2[y])}] += r[y]; } } int main() { liftt[0] = 1; for (int i = 1; i <= MAXN; i++) { liftt[i] = mul(liftt[i - 1], prime); } liftt2[0] = 1; for (int i = 1; i <= MAXN; i++) { liftt2[i] = mul(liftt2[i - 1], prime2); } 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); } 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); link(a, b); } else if (ty == 3) { if (cnt[{0, 0}] == n) { printf("DA\n"); } else { printf("NE\n"); } } else if (ty == 4) { printf("%lld\n", ans_for_4); } } return 0; }

Compilation message (stderr)

zamjene.cpp: In function 'int main()':
zamjene.cpp:204:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p[i]);
     ~~~~~^~~~~~~~~~~~~
zamjene.cpp:219:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ty);
     ~~~~~^~~~~~~~~~~
zamjene.cpp:222: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:237: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 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...