Good Bye 2014 A B C D E

const int N = 30005;

int n, t, a[N];

int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n – 1; i++)
scanf("%d", &a[i]);
int bo = 0;
for (int i = 1; i <= t;) {
if (i == t) {
bo = 1;
break;
}
i += a[i];
}
printf("%s
", bo ? "YES" : "NO");
return 0;
}

const int N = 305;

int n, a[N], g[N][N], vis[N];
char str[N];

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) {
scanf("%s", str);
for (int j = 0; j < n; j++)
g[i][j] = str[j] – '0';
g[i][i] = 1;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] |= (g[i][k]&g[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
int Min = n;
for (int j = 0; j < n; j++) {
if (g[j][i] && !vis[a[j]]) {
Min = min(Min, a[j]);
}
}
vis[Min] = 1;
printf("%d ", Min);
}
return 0;
}

const int N = 505;
typedef long long ll;

int n, m, w[N], vis[N][N];

int v;
ll sum = 0;

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i <= m; i++) {
scanf("%d", &v);
for (int j = 1; j <= n; j++)
sum += w[j] * vis[v][j];
memset(vis[v], 0, sizeof(vis[v]));
for (int j = 1; j <= n; j++) {
if (v == j) continue;
vis[j][v] = 1;
}
}
printf("%lld
", sum);
return 0;
}

const int N = 100005;

int n;

struct Edge {
int u, v, id, num;
double len;
Edge(){}
Edge(int u, int v, int id) {
this->u = u;
this->v = v;
this->id = id;
}
} e[N];

vector<Edge> g[N];

int dfs(int u, int p) {
int sz = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
if (v == p) continue;
int tmp = dfs(v, u);
sz += tmp;
e[g[u][i].id].num = tmp;
}
return sz;
}

int main() {
scanf("%d", &n);
int u, v;
double w;
for (int i = 1; i <= n – 1; i++) {
scanf("%d%d%lf", &u, &v, &w);
e[i].len = w;
g[u].push_back(Edge(u, v, i));
g[v].push_back(Edge(v, u, i));
}
dfs(1, 0);
int q;
scanf("%d", &q);
int id, vv;
double sum = 0;
for (int i = 1; i <= n – 1; i++) {
sum += (double)(n – 2) * (e[i].num) * (n – e[i].num) * (e[i].len);
}
double c1 = (double)n * (n – 1) * (n – 2) / 2 / 3;
while (q–) {
scanf("%d%d", &id, &vv);
sum -= (double)(n – 2) * (e[id].num) * (n – e[id].num) * (e[id].len – vv);
e[id].len = vv;
printf("%.10lf
", sum / c1);
}
return 0;
}

const int N = 200005;

struct query {
int l, r, id;
} s[N], q[N];

int n, ans[N];

bool cmp(query a, query b) {
return a.l > b.l;
}

int hash[N * 2], hn;

int find(int x) {
return lower_bound(hash, hash + hn, x) – hash;
}

#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)

struct Node {
int l, r, len, lazy;
void gao() {
lazy = 1;
len = 0;
}
} node[N * 8];

void pushup(int x) {
node[x].len = node[lson(x)].len + node[rson(x)].len;
}

void pushdown(int x) {
if (node[x].lazy) {
node[x].lazy = 0;
node[lson(x)].gao();
node[rson(x)].gao();
}
}

void build(int l, int r, int x = 0) {
node[x].l = l; node[x].r = r; node[x].lazy = 0;
if (l == r) {
node[x].len = hash[r + 1] – hash[l];
return;
}
int mid = (l + r) / 2;
build(l , mid, lson(x));
build(mid + 1, r, rson(x));
pushup(x);
}

void add(int l, int r, int x = 0) {
if (node[x].l >= l && node[x].r <= r) {
node[x].gao();
return;
}
pushdown(x);
int mid = (node[x].l + node[x].r) / 2;
if (l <= mid) add(l, r, lson(x));
if (r > mid) add(l, r, rson(x));
pushup(x);
}

int query(int l, int r, int x = 0) {
if (node[x].l >= l && node[x].r <= r)
return node[x].len;
int mid = (node[x].l + node[x].r) / 2;
int ans = 0;
pushdown(x);
if (l <= mid) ans += query(l, r, lson(x));
if (r > mid) ans += query(l, r, rson(x));
pushup(x);
return ans;
}

int main() {
scanf("%d", &n);
hn = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d", &s[i].l, &s[i].r);
s[i].r += s[i].l;
hash[hn++] = s[i].l;
hash[hn++] = s[i].r;
}
sort(hash, hash + hn);
hn = unique(hash, hash + hn) – hash;
build(0, hn – 2);
int qn;
scanf("%d", &qn);
for (int i = 0; i < qn; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].l–;
q[i].r–;
q[i].l = s[q[i].l].l;
q[i].r = s[q[i].r].l;
q[i].id = i;
}
sort(q, q + qn, cmp);
int now = n – 1;
for (int i = 0; i < qn; i++) {
while (s[now].l >= q[i].l && now >= 0) {
add(find(s[now].l), find(s[now].r) – 1);
now–;
}
ans[q[i].id] = query(find(q[i].l), find(q[i].r) – 1);
}
for (int i = 0; i < qn; i++)
printf("%d
", ans[i]);
return 0;
}