HackerEarth Potential problem solution

In this HackerEarth Potential problem solution Sometimes long stories are very boring. So we decided to make the statement as short as possible!

You have two integer arrays of size n: X and P. Your task is to perform q queries. There are three types of queries:

1. pos x: set Xpos = x
2. pos p: set Ppos = p
3. a b: find max{Xi + min(Pi, i - a)|i relate to [a,b]}

HackerEarth Potential problem solution.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define debug_flag 1
#else
    #define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
    os << "[" << p.first << ", " << p.second << "]";
    return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
    os << "[";
    bool first = true;
    for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
    {
        if (!first)
            os << ", ";
        first = false;
        os << *it;
    }
    os << "]";
    return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
    vector<string> v;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        v.emplace_back(x);
    return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
        cerr << name  << " = " << a << " ";
    else
        cerr << name << " ";
    _print(++it, args...);
}

typedef long long int int64;

const int N = 3e5 + 100;
const int B_SIZE = 400;
const int B_CNT = N / B_SIZE;
const int INF = (int)2e9 + (int)1e6;

void relax_max(int& a, int b) {
  a = max(a, b);
}

struct Item {
  int id, x, p;

  Item() : id(), x(), p() {}
  Item(int _id, int _x, int _p) :
    id(_id), x(_x), p(_p) {}

  bool operator < (const Item& other) const {
    int f = id - p;
    int other_f = other.id - other.p;
    return f < other_f;
  }
};

std::ostream& operator << (std::ostream& os, const Item &p) 
{
    os << "[id = " << p.id << ", x = " << p.x << ", p = " << p.p << "]";
    return os;
}

struct Query {
  int a, b, id;

  Query() : a(), b(), id() {}
  Query(int _a, int _b, int _id) :
    a(_a), b(_b), id(_id) {}

  bool operator < (const Query& other) const {
    return a < other.a;
  }
};

struct Block {
  Item item_list[B_SIZE];
  int ptr;
  int prefix_max[B_SIZE];
  int suffix_max[B_SIZE];

  Block() {}

  void init(int x_list[], int p_list[]) {
    for (int i = 0; i < B_SIZE; i++) {
      item_list[i] = Item(i, x_list[i], p_list[i]);
    }
    sort(item_list, item_list + B_SIZE);
    update_max();
  }

  void clear_ptr() {
    ptr = 0;
  }

  void update(int pos) {
    while (pos - 1 >= 0 && item_list[pos] < item_list[pos - 1]) {
      swap(item_list[pos], item_list[pos - 1]);
      pos--;
    }

    while (pos + 1 < B_SIZE && item_list[pos + 1] < item_list[pos]) {
      swap(item_list[pos], item_list[pos + 1]);
      pos++;
    }
    update_max();
  }

  void update_max() {
    for (int i = 0; i < B_SIZE; i++) {
      prefix_max[i] = item_list[i].x + item_list[i].id;
      if (i - 1 >= 0) {
        relax_max(prefix_max[i], prefix_max[i - 1]);
      }
    }

    for (int i = B_SIZE - 1; i >= 0; i--) {
      suffix_max[i] = item_list[i].x + item_list[i].p;
      if (i + 1 < B_SIZE) {
        relax_max(suffix_max[i], suffix_max[i + 1]);
      }
    }
  }

  int get_pos(int id) {
    for (int i = 0; i < B_SIZE; i++) {
      if (item_list[i].id == id) {
        return i;
      }
    }
    assert(false);
  }

  void set_x(int id, int x) {
    int pos = get_pos(id);
    item_list[pos].x = x;
    update(pos);
  }

  void set_p(int id, int p) {
    int pos = get_pos(id);
    item_list[pos].p = p;
    update(pos);
  }

  void set_xp(int id, int x, int p) {
    int pos = get_pos(id);
    item_list[pos].x = x;
    item_list[pos].p = p;
    update(pos);
  }

  void clear(int pos) {
    set_xp(pos, 0, -INF);
  }

  int solve(int sh0) {
    while (ptr < B_SIZE) {
      int sh = sh0 + item_list[ptr].id;
      int p = item_list[ptr].p;
      if (sh < p) {
        ptr++;
      } else {
        break;
      }
    }
    int ans = -INF;
    if (ptr - 1 >= 0) {
      int cur_ans = prefix_max[ptr - 1] + sh0;
      relax_max(ans, cur_ans);
    }
    if (ptr < B_SIZE) {
      int cur_ans = suffix_max[ptr];
      relax_max(ans, cur_ans);
    }
    return ans;
  }
};

int n, q;
int x_list[N], p_list[N];
int t_list[N], a_list[N], b_list[N];
int cur_x_list[N], cur_p_list[N];

int blocks_cnt;
Block block_list[B_CNT];

int ans_list[N];

int get_f(int pos, int a) {
  return cur_x_list[pos] + min(cur_p_list[pos], pos - a);
}

void solve(int l, int r) {
  vector<int> interesting_pos;
  for (int i = l; i <= r; i++) {
    if (t_list[i] == 1 || t_list[i] == 2) {
      interesting_pos.push_back(a_list[i]);
    }
  }
  sort(interesting_pos.begin(), interesting_pos.end());
  interesting_pos.erase(unique(interesting_pos.begin(), interesting_pos.end()),
      interesting_pos.end());
  for (int pos : interesting_pos) {
    int b = pos / B_SIZE;
    int pos_in_b = pos % B_SIZE;
    block_list[b].clear(pos_in_b);
  }

  for (int i = 0; i < n; i++) {
    cur_x_list[i] = x_list[i];
    cur_p_list[i] = p_list[i];
  }
  for (int pos : interesting_pos) {
    cur_x_list[pos] = 0;
    cur_p_list[pos] = -INF;
  }

  vector<Query> q_list;
  for (int i = l; i <= r; i++) {
    if (t_list[i] == 3) {
      q_list.push_back(Query(a_list[i], b_list[i], i));
    }
  }
  sort(q_list.begin(), q_list.end());
  for (int i = 0; i < blocks_cnt; i++) {
    block_list[i].clear_ptr();
  }
  for (const Query& query : q_list) {
    ans_list[query.id] = -INF;
    int new_a = query.a;
    int new_b = query.b;
    while (new_a % B_SIZE != 0 && new_a <= new_b) {
      relax_max(ans_list[query.id], get_f(new_a, query.a));
      new_a++;
    }
    while ((new_b + 1) % B_SIZE != 0 && new_a <= new_b) {
      relax_max(ans_list[query.id], get_f(new_b, query.a));
      new_b--;
    }
    for (int i = 0; i < blocks_cnt; i++) {
      int block_a = i * B_SIZE;
      int block_b = (i + 1) * B_SIZE - 1;
      if (new_a <= block_a && block_b <= new_b) {
        int cur_ans = block_list[i].solve(block_a - query.a);
        relax_max(ans_list[query.id], cur_ans);
      }
    }
  }

  for (int i = l; i <= r; i++) {
    if (t_list[i] == 1) {
      x_list[a_list[i]] = b_list[i];
    } else if (t_list[i] == 2) {
      p_list[a_list[i]] = b_list[i];
    } else {
      int cur_ans = -INF;
      for (int pos : interesting_pos) {
        if (a_list[i] <= pos && pos <= b_list[i]) {
          relax_max(cur_ans, x_list[pos] + min(p_list[pos], pos - a_list[i]));
        }
      }
      relax_max(ans_list[i], cur_ans);
    }
  }
  
  for (int pos : interesting_pos) {
    int b = pos / B_SIZE;
    int pos_in_b = pos % B_SIZE;
    block_list[b].set_xp(pos_in_b, x_list[pos], p_list[pos]);
  }
}

int main()
{
#ifdef LOCAL
    freopen ("input.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x_list[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &p_list[i]);
  }
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &t_list[i], &a_list[i], &b_list[i]);
    a_list[i]--;
    if (t_list[i] == 3) {
      b_list[i]--;
    }
  }

  blocks_cnt = (n + B_SIZE - 1) / B_SIZE;
  for (int i = 0; i < blocks_cnt; i++) {
    block_list[i].init(x_list + i * B_SIZE, p_list + i * B_SIZE);
  }

  for (int l = 0; l < q; l += B_SIZE) {
    int r = min(l + B_SIZE - 1, q - 1);
    solve(l, r);
  }

  for (int i = 0; i < q; i++) {
    if (t_list[i] == 3) {
      printf("%d\n", ans_list[i]);
    }
  }

    return 0;
}