Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.5 kB
2
Indexable
Never
#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;
}