2014
02-12

# Level up

Zty has met a big problem.His X Gu Niang was kidnaped by a secret organization.The organization only left Zty a letter:
"If you can beat our boss ,we will give her the freedom,or…"
The boss of the organization was so secret that no one knows his name.We only know that he was so powerful,and Zty is not powerful enough now,what he need to do is to train and to get more experience(Exp).Then he found a place wonderful for traning,There are N enemies there with different Exp,and Zty has M power ball,the number of power ball he used will effect the probability he beat the enemy.These probabilities are given as percentages pij, where i (with 1 ≤ i ≤ N) is the number of the enemy and j is the quantity of power balls used on it.One power ball can be used only once.
Zty has to level up to 99,then he will be able to beat the boss.Of cause he is level 1 at the begining.He want to know weather the maximal expected Exp he can get is enough.The expected Exp is calculated as Sum(P(i)*Exp) where P is the probability.
The Exp Zty need to level up one level is K/100 , and K will be given.

Notice that: If Zty doesn’t used a power ball,the probability he beat the enemy is 0. ^_^

The first line contain a T ,then T cases followed.Each test case has the following format:
One line with one integer K <= 100000: as the description means.
One line with one integer N with 1 ≤ N ≤ 100: the number of enemies.
One line with one integer M with 0 ≤ M ≤ 100: the maximal number of available power ball.
One line with N integers indicating the Exp of the N enemies.
N lines, each line corresponding to a enemy i, containing n integers pi1, pi2, …, pim (the percentages, with 0 ≤ pi1, pi2, …, pim ≤ 100).

The first line contain a T ,then T cases followed.Each test case has the following format:
One line with one integer K <= 100000: as the description means.
One line with one integer N with 1 ≤ N ≤ 100: the number of enemies.
One line with one integer M with 0 ≤ M ≤ 100: the maximal number of available power ball.
One line with N integers indicating the Exp of the N enemies.
N lines, each line corresponding to a enemy i, containing n integers pi1, pi2, …, pim (the percentages, with 0 ≤ pi1, pi2, …, pim ≤ 100).

2
1000
2
4
8 975
85 94 93 100
0 0 100 100
1000
1
4
979
0 0 0 100

Love you Ten thousand years.
Cry,men,not crime.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

const int inf = 0x3f3f3f3f;
const int maxn = 10010;
int val[maxn];

struct SegNode {
int left, right, exp, level, lazy, min_;
int mid() {
return (left + right) >> 1;
}
};

struct SegmentTree {
SegNode tree[maxn*5];

void PushUp(int idx) {
tree[idx].exp = std::max(tree[idx<<1].exp, tree[idx<<1|1].exp);
tree[idx].level = std::max(tree[idx<<1].level, tree[idx<<1|1].level);
tree[idx].min_ = std::min(tree[idx<<1].min_, tree[idx<<1|1].min_);
}

void PushDown(int idx) {
tree[idx<<1].exp += tree[idx].lazy * tree[idx<<1].level;
tree[idx<<1].min_ -= tree[idx].lazy;
tree[idx<<1].lazy += tree[idx].lazy;
tree[idx<<1|1].exp += tree[idx].lazy * tree[idx<<1|1].level;
tree[idx<<1|1].min_ -= tree[idx].lazy;
tree[idx<<1|1].lazy += tree[idx].lazy;
tree[idx].lazy = 0;
}

void build(int left, int right, int idx) {
tree[idx].left = left; tree[idx].right = right;
tree[idx].exp = 0; tree[idx].level = 1;
tree[idx].lazy = 0; tree[idx].min_ = val[1];
if (left == right) return ;
int mid = (left + right) >> 1;
build(left, mid, idx<<1);
build(mid + 1, right, idx<<1|1);
PushUp(idx);
}

void update(int left, int right, int idx, int value) {
if (tree[idx].left == tree[idx].right) {
tree[idx].exp += tree[idx].level * value;
while (tree[idx].exp >= val[tree[idx].level])
tree[idx].level++;
tree[idx].min_ = (val[tree[idx].level] - tree[idx].exp) / tree[idx].level;
return ;
}
if (tree[idx].left == left && tree[idx].right == right) {
if (value >= tree[idx].min_) {
PushDown(idx);
int mid = (left + right) / 2;
update(left, mid, idx << 1, value);
update(mid + 1, right, idx << 1 | 1, value);
PushUp(idx);
} else {
tree[idx].exp += tree[idx].level * value;
tree[idx].min_ -= value;
tree[idx].lazy += value;
}
return ;
}
int mid = tree[idx].mid();
if (tree[idx].lazy)
PushDown(idx);
if (mid >= right)
update(left, right, idx << 1, value);
else if (mid < left)
update(left, right, idx << 1 | 1, value);
else {
update(left, mid, idx << 1, value);
update(mid + 1, right, idx << 1 | 1, value);
}
PushUp(idx);
}

int query(int left, int right, int idx) {
if (tree[idx].left == left && tree[idx].right == right)
return tree[idx].exp;
if (tree[idx].lazy)
PushDown(idx);
int mid = tree[idx].mid();
if (mid >= right)
return query(left, right, idx << 1);
else if (mid < left)
return query(left, right, idx << 1 | 1);
else
return std::max(query(left, mid, idx<<1), query(mid+1, right, idx<<1|1));
}
};

SegmentTree seg;

int main() {
int test, n, k, q, left, right, value;
char ch[111];
scanf("%d", &test);
for (int cas = 1; cas <= test; cas++) {
scanf("%d %d %d", &n, &k, &q);
for (int i = 1; i < k; i++)
scanf("%d", &val[i]);
val[k] = inf;
printf("Case %d:\n", cas);
seg.build(1, n, 1);
for (int qq = 1; qq <= q; qq++) {
scanf("%s", ch);
if (ch[0] == 'W') {
scanf("%d %d %d", &left, &right, &value);
seg.update(left, right, 1, value);
} else {
scanf("%d %d", &left, &right);
printf("%d\n", seg.query(left, right, 1));
}
}
puts("");
}
return 0;
}

1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

2. #include <cstdio>

int main() {