In this HackerEarth Mathison and the problem of the Pokemon fight solution, Mathison has decided to become a Pokémon master. In order to do that he has to gain some experience by fighting in a lot of tournaments, some of which can take quite a lot of time.
Recently, he has signed up for a new one, among other N contestants. Each Pokémon trainer has to use exactly two Pokémons, a primary and a secondary, each having some value. There are s few rules about how the competition should be structured but they are way too complicated to explain here. The rules about fighting are simple and are easily explained below.
A fight can only be carried between Pokémons of equal value (otherwise it would be clear who the winner is). However, this is way too restrictive and the judges have come up with a compromise. A fight can also contain a training period. Basically, the weaker Pokémon spends some time in the PokeGym to become as good as the other one (one second of hard work is required to gain one hitpoint). The actual fight takes place instantly. To sum up: a fight between two Pokémons of values a and b lasts exactly |a - b| seconds.
A fight between two trainers is actually made from two fights, one between the primary Pokémons and one between the secondary Pokémons, that run at the same time (i.e. they run in parallel). The length of the whole fight is the maximum duration between the two fights.
HackerEarth Mathison and the Pokémon fight problem solution.
#include <bits/stdc++.h>
using namespace std;
const int BUFFER_SIZE = (1 << 16);
char buffer[BUFFER_SIZE];
int position = BUFFER_SIZE;
inline char getChar()
{
if ( position == BUFFER_SIZE )
{
position = 0;
fread(buffer, BUFFER_SIZE, 1, stdin);
}
return buffer[position++];
}
inline int getInt()
{
register int a = 0;
char ch;
int sgn = 1;
do
{
ch = getChar();
} while ( !isdigit(ch) && ch != '-' );
if ( ch == '-' )
{
sgn = -1;
ch = getChar();
}
do
{
a = (a << 3) + (a << 1) + ch - '0';
ch = getChar();
} while ( isdigit(ch) );
return a * sgn;
}
class Normalization{
private:
unordered_map<int, int> umap;
int value;
public:
Normalization(vector<int> xs){
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
value = 0;
for (auto x: xs)
umap[x] = ++value;
}
int operator[] (const int &key) const{
auto it = umap.find(key);
assert(it != umap.end());
return it->second;
}
size_t size() const{
return value;
}
};
class Change{
public:
int type; // update: 0 | query: 1
long long x; // update: old_value | query: key
long long y; // update: new_value | query: not defined
int id; // update & query: id of generating operation
};
class FenwickTree{
private:
vector<long long> sum_tree;
vector<int> cnt_tree;
static int lsb(int x){
return x & (-x);
}
public:
FenwickTree(size_t n){
sum_tree.resize(n + 1);
cnt_tree.resize(n + 1);
}
void update(int key, int value, int to_add){
assert(0 < key);
while (key < (int)sum_tree.size()){
sum_tree[key] += value;
cnt_tree[key] += to_add;
key += lsb(key);
}
}
pair<long long, int> query(int key){
assert(key >= 0);
long long sum = 0;
int cnt = 0;
while (key > 0){
sum += sum_tree[key];
cnt += cnt_tree[key];
key -= lsb(key);
}
return {sum, cnt};
}
};
class SegmentTree{
private:
vector<vector<Change>> changesX, changesY;
vector<vector<int>> xs, ys;
vector<int> Xs, Ys;
int N;
void build(int node, int l, int r){
for (int k = l; k <= r; k++){
xs[node].push_back(Xs[k]);
ys[node].push_back(Ys[k]);
}
if (l != r){
int m = (l + r) / 2;
build(2 * node, l, m);
build(2 * node + 1, m + 1, r);
}
}
void update(int node, int l, int r, int pos, const Change &updateX, const Change &updateY){
changesX[node].emplace_back(updateX);
changesY[node].emplace_back(updateY);
xs[node].push_back(updateX.y);
ys[node].push_back(updateY.y);
if (l != r){
int m = (l + r) / 2;
if (pos <= m)
update(2 * node, l, m, pos, updateX, updateY);
else
update(2 * node + 1, m + 1, r, pos, updateX, updateY);
}
}
void query(int node, int l, int r, const int &st_q, const int &dr_q, const Change &queryX, const Change &queryY){
if (st_q <= l && r <= dr_q){
changesX[node].emplace_back(queryX);
changesY[node].emplace_back(queryY);
xs[node].push_back(queryX.x);
ys[node].push_back(queryY.x);
}
else{
int m = (l + r) / 2;
if (st_q <= m)
query(2 * node, l, m, st_q, dr_q, queryX, queryY);
if (m < dr_q)
query(2 * node + 1, m + 1, r, st_q, dr_q, queryX, queryY);
}
}
void solve(int node, int l, int r){
Normalization normX(xs[node]);
Normalization normY(ys[node]);
FenwickTree bitX(normX.size());
FenwickTree bitY(normY.size());
long long total_sum_x = 0;
long long total_sum_y = 0;
for (int k = l; k <= r; k++){
bitX.update(normX[Xs[k]], Xs[k], +1);
bitY.update(normY[Ys[k]], Ys[k], +1);
total_sum_x += Xs[k];
total_sum_y += Ys[k];
}
auto perform_changes = [this, node, l, r](vector<vector<Change>> &changes, Normalization &norm, FenwickTree &bit, long long &total_sum){
for (size_t it = 0; it < changes[node].size(); it++){
size_t i = it;
int t = changes[node][i].type;
// update
if (t == 0){
auto old_value = changes[node][i].x;
auto new_value = changes[node][i].y;
bit.update(norm[old_value], -old_value, -1);
bit.update(norm[new_value], new_value, +1);
total_sum = total_sum - old_value + new_value;
} else{
// query
auto key = changes[node][i].x;
auto p = bit.query(norm[key]);
solutions[changes[node][i].id] += (key * p.second - p.first) + ((total_sum - p.first) - (r - l + 1 - p.second) * key);
}
}
};
perform_changes(changesX, normX, bitX, total_sum_x);
perform_changes(changesY, normY, bitY, total_sum_y);
if (l != r){
int m = (l + r) / 2;
solve(2 * node, l, m);
solve(2 * node + 1, m + 1, r);
}
}
public:
vector<long long> solutions;
SegmentTree(const vector<int> &Xs, const vector<int> &Ys) {
this->N = (int)Xs.size();
assert(Xs.size() == Ys.size());
changesX.resize(4 * N);
changesY.resize(4 * N);
xs.resize(4 * N);
ys.resize(4 * N);
this->Xs = Xs;
this->Ys = Ys;
build(1, 0, N - 1);
}
void update(int pos, const Change &updateX, const Change &updateY){
update(1, 0, N - 1, pos - 1, updateX, updateY);
}
void query(int x, int y, const Change &queryX, const Change &queryY){
query(1, 0, N - 1, x - 1, y - 1, queryX, queryY);
}
void solve(){
solve(1, 0, N - 1);
}
};
using Point = pair<int, int>;
Point transform(Point A){
return make_pair(A.first + A.second, A.first - A.second);
}
Point read_point(){
int a = getInt();
int b = getInt();
assert(abs(a) <= 1000000000);
assert(abs(b) <= 1000000000);
return make_pair(a, b);
}
class UpdateOrQuery{
public:
int t;
int i, j;
int px, py;
int id;
};
int main(){
ios_base::sync_with_stdio(false);
int N, Q;
N = getInt();
Q = getInt();
vector<Point> teams(N);
vector<int> Xs, Ys;
for (int i = 0; i < N; i++){
auto P = transform(read_point());
Xs.push_back(P.first);
Ys.push_back(P.second);
}
SegmentTree seg_tree(Xs, Ys);
vector<int> queries;
for (int id = 0; id < Q; id++){
int t = getInt();
assert(0 <= t && t <= 1);
if (t == 0){
int p = getInt();
assert(1 <= p && p <= N);
auto P = transform(read_point());
Change updateX{0, Xs[p - 1], P.first, id};
Change updateY{0, Ys[p - 1], P.second, id};
seg_tree.update(p, updateX, updateY);
Xs[p - 1] = P.first;
Ys[p - 1] = P.second;
}
else{
int i = getInt();
int j = getInt();
assert(1 <= i && i <= j && j <= N);
auto P = transform(read_point());
Change queryX{1, P.first, -1, id};
Change queryY{1, P.second, -1, id};
seg_tree.query(i, j, queryX, queryY);
queries.push_back(id);
}
}
seg_tree.solutions.resize(Q);
seg_tree.solve();
for (int q: queries)
cout << seg_tree.solutions[q] / 2 << "\n";
return 0;
}
0 Comments