#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
#define MAX_STOCK_LEN 10
struct stock {
int id;
int price;
string name;
}stocks[MAX];
struct node {
int id;
int diff;
};
int lazy[4 * MAX];
node seg[4 * MAX];
unordered_map<string, int> umap;
node check(node a, node b) {
if (a.diff != b.diff)
return (a.diff > b.diff) ? a : b;
return (a.id < b.id) ? a : b;
}
int n;
void makeSegment(int index, int left, int right) {
if (left == right) {
seg[index].id = stocks[left].id;
return;
}
if (left > right)
return;
int mid = (left + right) / 2;
makeSegment(index * 2 + 1, left, mid);
makeSegment(index * 2 + 2, mid + 1, right);
seg[index] = check(seg[index * 2 + 1] , seg[index * 2 + 2]);
}
void rangeUpdateByLazy(int index, int left, int right, int x, int y, int val) {
if (lazy[index] != 0) {
seg[index].diff += lazy[index];
if (left != right) {
lazy[index * 2 + 1] += lazy[index];
lazy[index * 2 + 2] += lazy[index];
}
lazy[index] = 0;
}
if (left >= x && right <= y) {
seg[index].diff += val;
if (left != right) {
lazy[index * 2 + 1] += val;
lazy[index * 2 + 2] += val;
}
return;
}
if (left > y || right < x || left > right)
return;
int mid = (left + right) / 2;
rangeUpdateByLazy(index * 2 + 1, left, mid, x, y, val);
rangeUpdateByLazy(index * 2 + 2, mid + 1, right, x, y, val);
seg[index] = check(seg[index * 2 + 1], seg[index * 2 + 2]);
}
node getRangeQueryLazy(int index, int left, int right, int x, int y) {
if (lazy[index] != 0) {
seg[index].diff += lazy[index];
if (left != right) {
lazy[index * 2 + 1] += lazy[index];
lazy[index * 2 + 2] += lazy[index];
}
lazy[index] = 0;
}
if (left >= x && right <= y)
return seg[index];
if (left > y || right < x || left > right)
return { -1,INT_MIN };;
int mid = (left + right) / 2;
return check(getRangeQueryLazy(index * 2 + 1, left, mid, x, y) , getRangeQueryLazy(index * 2 + 2, mid + 1, right, x, y));
}
bool compare(stock& a, stock& b) {
return a.name < b.name;
}
void init(int N, char mStocks[][MAX_STOCK_LEN + 1], int mPrices[])
{
n = N;
umap.clear();
for (int i = 0; i < 4 * MAX; i++)
{
seg[i].diff = 0;
seg[i].id = -1;
lazy[i] = 0;
}
for (int i = 0; i < n; i++)
{
stocks[i].id = i;
stocks[i].name = mStocks[i];
stocks[i].price = mPrices[i];
}
sort(stocks, stocks + n, compare);
for (int i = 0; i < n; i++)
{
umap[stocks[i].name] = i;
}
makeSegment(0, 0, n - 1);
}
void changePrices(char mFromStock[], char mToStock[], int mPriceDiff)
{
int l = umap[mFromStock];
int r = umap[mToStock];
rangeUpdateByLazy(0, 0, n - 1, l, r, mPriceDiff);
}
int getPrice(char mStock[])
{
int it = umap[mStock];
node n1 = getRangeQueryLazy(0, 0, n - 1, it, it);
return stocks[it].price + n1.diff;
}
int getMostIncreasedStock(char mFromStock[], char mToStock[])
{
int l = umap[mFromStock];
int r = umap[mToStock];
node res = getRangeQueryLazy(0, 0, n - 1, l, r);
return res.id;
}