Submission #234804

#	Time	Username	Problem	Language	Result	Execution time	Memory
234804		AlexLuchianov	Two Antennas (JOI19_antennas)	C++14	100 / 100	917 ms	43352 KiB

antennas

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const inf = 1000000005;

struct El{
  int h;
  int a;
  int b;
} v[1 + nmax];
int _queries[1 + nmax][2];
int sol[1 + nmax];

vector<int> events[1 + nmax];
vector<pair<int,int>> queries[1 + nmax];

class SegmentTree{
private:
  struct Node{
    int result;
    int smax;
    Node operator + (Node const &a) const {
      return {max(result, a.result), max(smax, a.smax)};
    }
  };
public:
  vector<Node> aint;
  vector<int> lazy;

  SegmentTree(int n){
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }

  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
    aint[node] = {-inf, -inf};
  }

  void cleannode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] = max(lazy[node * 2], lazy[node]);
      lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
    }
    aint[node].result = max(aint[node].result, aint[node].smax + lazy[node]);
    lazy[node] = 0;
  }

  void computenode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      aint[node] = aint[node * 2] + aint[node * 2 + 1];
    }
  }

  void update(int node, int from, int to, int x, int y, int val){
    if(x == from && to == y){
      lazy[node] = max(lazy[node], val);
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  void setvalue(int node, int from, int to, int x, int val){
    if(from < to){
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        setvalue(node * 2, from, mid, x, val);
      else
        setvalue(node * 2 + 1, mid + 1, to, x, val);
      computenode(node, from, to);
    } else {
      cleannode(node, from, to);
      aint[node].smax = val;
    }
  }

  int query(int node, int from, int to, int x, int y){
    cleannode(node, from, to);
    if(from == x && to == y)
      return aint[node].result;
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

void solve(int n, int q){
  for(int i = 1;i <= n; i++) {
    events[i].clear();
    queries[i].clear();
  }

  for(int i = 1; i <= n; i++) {
    if(i + v[i].a <= n)
      events[i + v[i].a].push_back(i);
    if(i + v[i].b + 1 <= n)
      events[i + v[i].b + 1].push_back(-i);
  }

  for(int i = 1; i <= q; i++)
    queries[_queries[i][1]].push_back({_queries[i][0], i});
  SegmentTree aint(1 + n);
  aint.build(1, 1, n);

  for(int i = 1; i <= n; i++)
    aint.setvalue(1, 1, n, i, -inf);

  for(int i = 1; i <= n; i++){
    for(int h = 0; h < events[i].size(); h++){
      int id = events[i][h];
      if(0 < id)
        aint.setvalue(1, 1, n, id, -v[id].h);
      else
        aint.setvalue(1, 1, n, -id, -inf);
    }

    int x = max(1, i - v[i].b);
    int y = i - v[i].a;
    if(x <= y)
      aint.update(1, 1, n, x, y, v[i].h);


    for(int h = 0; h < queries[i].size(); h++){
      int pos = queries[i][h].second;
      sol[pos] = max(sol[pos], aint.query(1, 1, n, queries[i][h].first, i));
    }
  }
}

int oth(int n, int pos){
  return n - pos + 1;
}

int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);


  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i].h >> v[i].a >> v[i].b;
  int q;
  cin >> q;
  for(int i = 1;i <= q; i++)
    cin >> _queries[i][0] >> _queries[i][1];
  for(int i = 1;i <= q; i++)
    sol[i] = -1;

  solve(n, q);

  for(int i = 1;i <= n; i++)
    if(i < oth(n, i))
      swap(v[i], v[oth(n, i)]);
  for(int i = 1;i <= q; i++) {
    _queries[i][0] = oth(n, _queries[i][0]);
    _queries[i][1] = oth(n, _queries[i][1]);
    swap(_queries[i][0], _queries[i][1]);
  }

  solve(n, q);
  for(int i = 1;i <= q; i++)
    cout << sol[i] << '\n';

  return 0;
}

Compilation message (stderr)

antennas.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
antennas.cpp:54:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In member function 'void SegmentTree::computenode(int, int, int)':
antennas.cpp:64:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In function 'void solve(int, int)':
antennas.cpp:139:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < events[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
antennas.cpp:153:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queries[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65