結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2019-08-07 12:31:48 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 32,896 KB |
実行使用メモリ | 25,244 KB |
最終ジャッジ日時 | 2024-10-14 02:00:09 |
合計ジャッジ時間 | 2,053 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <string.h>#include <math.h>#include <limits.h>#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) > (b) ? (b) : (a))#define abs(x) ((x) > 0 ? (x) : -(x))#define rep(i, n) for(int i = 0; i < (n); i++)#define INF 1000000000000 //10^12#define MOD 1000000007 //10^9 + 7#define endl printf("\n")typedef long long ll;#define MAX_N 300010ll n, dat[2 * MAX_N - 1];voidinit(ll n_){n = 1;while (n < n_) {n *= 2;}for (int i = 0; i < 2 * n - 1; i++) {dat[i] = 0;}}voidupdate(ll k, ll a){k += n - 1;dat[k] += a;while (k > 0) {k = (k - 1) / 2;dat[k] = dat[2 * k + 1] + dat[2 * k + 2];}}//[a, b)の和を求めるintquery(ll a, ll b, ll k, ll l, ll r){if (r <= a || b <= l) {return 0;}if (a <= l && r <= b) {return dat[k];} else {ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return vl + vr;}}typedef struct { ll u, v; } E;intasort(const void *a, const void *b){E x = *(E *)a, y = *(E *)b;if (x.u > y.u) return 1;if (x.u < y.u) return -1;return 0;}ll cnt = 0;voiddfs(ll i, E *e, ll *id){update(i, 1);cnt += query(0, i, 0, 0, n);for (ll j = id[i]; j < id[i + 1]; j++) {if (dat[n - 1 + e[j].v] == 0) {dfs(e[j].v, e, id);}}update(i, -1);return;}intmain(int argc, char **argv){ll m;scanf("%lld", &m);E e[300010];ll a;for (int i = 1; i < m; i++) {scanf("%lld", &a);e[i - 1].u = a;e[i - 1].v = i;}qsort(e, m - 1, sizeof(E), asort);ll id[300010];id[0] = 0;ll p = 0;for (ll i = 0; i < m; i++){while(e[p].u < i && p < m - 1) p++;id[i] = p;}id[m] = m - 1;init(m);dfs(0, e, id);printf("%lld\n", cnt);return 0;}