Submission #1127398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127398		duckindog	Two Antennas (JOI19_antennas)	C++20	100 / 100	617 ms	38340 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, q;
struct Atten { 
  int h, x, y;
  friend istream& operator >> (istream& is, Atten& rhs) { 
    return is >> rhs.h >> rhs.x >> rhs.y;
  }
} atten[N];
struct Query { 
  int l, r;
  friend istream& operator >> (istream& is, Query& rhs) { 
    return is >> rhs.l >> rhs.r;
  }
} query[N];

namespace IT { 
  const int MAX = 1'000'000'001;
  struct Node { 
    int a, value;
    Node(int a = 0, int value = -1) : a(a), value(value) {}
  } f[N << 2];
  int lazy[N << 2];

  Node merge(const Node& lt, const Node& rt) { 
    Node ret;
    ret.a = max(lt.a, rt.a);
    ret.value = max(lt.value, rt.value);
    return ret;
  }

  void build(int s, int l, int r) { 
    f[s] = Node();
    lazy[s] = MAX;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  }

  void push(int s) { 
    if (lazy[s] == MAX) return;
    f[s << 1].value = max(f[s << 1].value, f[s << 1].a - lazy[s]);
    lazy[s << 1] = min(lazy[s << 1], lazy[s]);

    f[s << 1 | 1].value = max(f[s << 1 | 1].value, f[s << 1 | 1].a - lazy[s]);
    lazy[s << 1 | 1] = min(lazy[s << 1 | 1], lazy[s]);

    lazy[s] = MAX;
  }
  void updateA(int s, int l, int r, int p, int x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s].a = x;
      return;
    }
    push(s);
    int mid = (l + r) >> 1;
    updateA(s << 1, l, mid, p, x); updateA(s << 1 | 1, mid + 1, r, p, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
  }
  void updateB(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      lazy[s] = min(lazy[s], x);
      f[s].value = max(f[s].value, f[s].a - x);
      return;
    }
    push(s);
    int mid = (l + r) >> 1;
    updateB(s << 1, l, mid, u, v, x); updateB(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
  }
  Node query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return Node();
    if (u <= l && r <= v) return f[s];
    push(s);
    int mid = (l + r) >> 1;
    return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
}

vector<int> saveQuery[N];
vector<pair<int, int>> saveUpdate[N];

int answer[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> atten[i];
  cin >> q;
  for (int i = 1; i <= q; ++i) cin >> query[i];

  memset(answer, -1, sizeof answer);
  IT::build(1, 1, n);
  for (int turn = 0; turn < 2; ++turn) { 
    IT::build(1, 1, n);
    for (int i = 1; i <= n; ++i) { 
      const auto& [h, x, y] = atten[i];
      saveUpdate[min(n + 1, i + x)].push_back({1, i});
      saveUpdate[min(n + 1, i + y + 1)].push_back({-1, i});
    }
    for (int i = 1; i <= q; ++i) { 
      const auto& [l, r] = query[i];
      saveQuery[r].push_back(i);
    }

    for (int i = 1; i <= n; ++i) { 
      for (const auto& [type, idx] : saveUpdate[i]) { 
        if (type == 1) IT::updateA(1, 1, n, idx, atten[idx].h);
        else IT::updateA(1, 1, n, idx, 0);
      }
      IT::updateB(1, 1, n, i - atten[i].y, i - atten[i].x, atten[i].h);

      for (const auto& idx : saveQuery[i]) { 
        const auto& [l, r] = query[idx];
        answer[idx] = max(answer[idx], IT::query(1, 1, n, l, r).value);
      }
    } 
    
    { // clear
      for (int i = 1; i <= n; ++i) { 
        saveUpdate[i].clear();
        saveQuery[i].clear();
      }
    }
    { // rotate
      reverse(atten + 1, atten + n + 1);
      for (int i = 1; i <= q; ++i) { 
        auto& [l, r] = query[i];
        tie(l, r) = make_pair(n - r + 1, n - l + 1);
      }
    }
  }

  for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}

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