Submission #197311

#	Time	Username	Problem	Language	Result	Execution time	Memory
197311		quocnguyen1012	Two Antennas (JOI19_antennas)	C++14	100 / 100	1470 ms	57612 KiB

antennas

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;
const ll inf = 1e17;

class seg_tree
{
  vector<ll> C, lazy, D;
public:
  seg_tree(int n)
  {
    C.assign(4 * n + 5, -inf);
    lazy.assign(4 * n + 5, inf);
    D.assign(4 * n + 5, -inf);
  }
  #define lc id << 1
  #define rc id << 1 | 1
  void dolazy(int id, int l, int r)
  {
    if (lazy[id] != inf && l != r){
      lazy[lc] = min(lazy[lc], lazy[id]);
      lazy[rc] = min(lazy[rc], lazy[id]);
      D[lc] = max(D[lc], C[lc] - lazy[lc]);
      D[rc] = max(D[rc], C[rc] - lazy[rc]);
    }
    lazy[id] = inf;
  }
  void merges(int id)
  {
    C[id] = max(C[lc], C[rc]);
    D[id] = max(D[lc], D[rc]);
  }
  void down(int id, int l, int r, int pos, ll val)
  {
    dolazy(id, l, r);
    if (l > pos || r < pos)
      return;
    if (l == r){
      C[id] = val;
      return;
    }
    int mid = (l + r) / 2;
    down(lc, l, mid, pos, val); down(rc, mid + 1, r, pos, val);
    merges(id);
  }
  void update(int id, int l, int r, int L, int R, ll val)
  {
    dolazy(id, l, r);
    if (l > R || L > r || L > R) return;
    if (L <= l && r <= R){
      lazy[id] = val;
      D[id] = max(D[id], C[id] - lazy[id]);
      return;
    }
    int mid = (l + r) / 2;
    update(lc, l, mid, L, R, val); update(rc, mid + 1, r, L, R, val);
    merges(id);
  }
  ll getmax(int id, int l, int r, int L, int R)
  {
    dolazy(id, l, r);
    if (l > R || L > r) return -inf;
    if (L <= l && r <= R){
      return D[id];
    }
    int mid = (l + r) / 2;
    return max(getmax(lc, l, mid, L, R), getmax(rc, mid + 1, r, L, R));
  }
  #undef lc
  #undef rc
};

class Query
{
public:
  int l, r;
};

int N, Q;
vector<int> add[maxn], del[maxn];
ll H[maxn]; int A[maxn], B[maxn];
vector<int> ask[maxn];
Query query[maxn];
ll res[maxn];

void solve(void)
{
  for (int i = 1; i <= N; ++i){
    add[i].clear(); del[i].clear();
    ask[i].clear();
  }
  for (int i = 1; i <= N; ++i){
    int s = i + A[i], e = i + B[i] + 1;
    if (s <= N) add[s].pb(i);
    if (e <= N) del[e].pb(i);
  }
  for (int i = 1; i <= Q; ++i){
    ask[query[i].r].pb(i);
  }
  seg_tree tree(N);
  for (int i = 1; i <= N; ++i){
    for (auto & id : add[i])
      tree.down(1, 1, N, id, H[id]);
    for (auto & id : del[i])
      tree.down(1, 1, N, id, -inf);
    int s = max(0, i - A[i]), e = i - B[i];
    tree.update(1, 1, N, max(1, e), s, H[i]);
    for (auto & id : ask[i]){
      int l = query[id].l;
      res[id] = max(res[id], tree.getmax(1, 1, N, l, i));
    }
  }
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  for (int i = 1; i <= N; ++i){
    cin >> H[i] >> A[i] >> B[i];
  }
  cin >> Q;
  for (int i = 1; i <= Q; ++i){
    cin >> query[i].l >> query[i].r;
    res[i] = -1;
  }
  solve();
  reverse(H + 1, H + 1 + N);
  reverse(A + 1, A + 1 + N);
  reverse(B + 1, B + 1 + N);
  for (int i = 1; i <= Q; ++i){
    query[i].l = N - query[i].l + 1;
    query[i].r = N - query[i].r + 1;
    swap(query[i].l, query[i].r);
  }
  solve();
  for (int i = 1; i <= Q; ++i) cout << res[i] << '\n';
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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