Submission #3342

#TimeUsernameProblemLanguageResultExecution timeMemory
3342wookayin0 = not cute / 1 = cute (kriii1_0)C++98
0 / 1
0 ms1992 KiB
#include <cstdio> #include <map> using namespace std; int n; int uf[100001]; int sz[100001]; int find(int x) { if(uf[x] == x) return x; else return uf[x] = find(uf[x]); } struct info { int m1, m2; int p; }; info merge(int i, int j) { i = find(i), j = find(j); info ret; ret.m1 = sz[i]; ret.m2 = sz[j]; // uf[i] = j uf[i] = j; sz[j] += sz[i]; sz[i] = 0; ret.p = sz[j]; return ret; } int nextInt() { int t; scanf("%d", &t); return t; } struct P { long long first; long long second; P(long long first, long long second) : first(first), second(second) {} }; long long go(long long k, int w) { return k*(k-1)/2*w; } long long go2(long long k, int w) { return k*(k-1)*(k+1)/6*w; } int main() { n = nextInt(); map<int, int> a; a[1] = n; for(int i = 0; i < n; ++ i) uf[i] = i, sz[i] = 1; long long ans1 = go(1LL, n); long long ans2 = go2(1LL, n); for(int i = 0; i < n - 1; ++ i) { int p = nextInt() - 1; info in = merge(p, p+1); ans1 = ans1 - go(in.m1, a[in.m1]); ans1 = ans1 - go(in.m2, a[in.m2]); ans2 = ans2 - go2(in.m1, a[in.m1]); ans2 = ans2 - go2(in.m2, a[in.m2]); a[in.m1] --; a[in.m2] --; a[in.p] ++; ans1 = ans1 + go(in.p, a[in.p]); ans2 = ans2 + go2(in.p, a[in.p]); printf("%lld %lld\n", ans1, ans2); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...