제출 #261531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261531		Bruteforceman	Two Antennas (JOI19_antennas)	C++11	0 / 100	185 ms	100216 KiB

antennas

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
const int maxn = 2e5 + 10;
const long long inf = 1e16;
int n;
struct data {
  int h, b, e;
  data (int h, int b, int e) : h(h), b(b), e(e) {}
  data () {}
} a[maxn];
struct node {
  long long opt;
  long long minh, maxh;
  long long minval, maxval;
  void init() {
    opt = -inf;
    minh = minval = inf;
    maxh = maxval = -inf;
  }
  node () {
    this -> init();
  }
} t[maxn * 4];
vector <pii> v[maxn];
long long ans[maxn];

void merge(node &c, node d) {
  c.minval = min(c.minval, d.minval);
  c.maxval = max(c.maxval, d.maxval);
  c.opt = max({c.opt, c.maxval - c.minh, c.maxh - c.minval});
}
void upd(int c) {
  int l = c << 1;
  int r = l + 1;
  t[c].opt = max(t[l].opt, t[r].opt);
  t[c].maxh = max(t[l].maxh, t[r].maxh);
  t[c].minh = min(t[l].minh, t[r].minh);
}
void pushdown(int c) {
  int l = c << 1;
  int r = l + 1;
  merge(t[l], t[c]);
  merge(t[r], t[c]);
  t[c].init();
  upd(c);
  return ;
}
void update(int x, int y, long long val, int c = 1, int b = 1, int e = n) {
  if(x <= b && e <= y) {
    node aux;
    aux.minval = aux.maxval = val;
    merge(t[c], aux);
    return ;
  }
  if(y < b || e < x) return ;
  pushdown(c);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  update(x, y, val, l, b, m);
  update(x, y, val, r, m + 1, e); 
  upd(c);
}
void add(int x, int c = 1, int b = 1, int e = n) {
  if(b == e) {
    t[c].init();
    t[c].minh = t[c].maxh = a[x].h;
    return ;
  }
  pushdown(c);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) add(x, l, b, m);
  else add(x, r, m + 1, e);
  upd(c);
}
void del(int x, int c = 1, int b = 1, int e = n) {
  if(b == e) {
    int aux = t[c].opt;
    t[c].init();
    t[c].opt = aux;
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) del(x, l, b, m);
  else del(x, r, m + 1, e);
  upd(c);
}
long long query(int x, int y, int c = 1, int b = 1, int e = n) {
  if(x <= b && e <= y) return t[c].opt;
  if(y < b || e < x) return -inf;
  pushdown(c);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return max(query(x, y, l, b, m), query(x, y, r, m + 1, e));
}
vector <int> start[maxn], fin[maxn];

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d %d %d", &a[i].h, &a[i].b, &a[i].e);
  }
  int q;
  scanf("%d", &q);
  for(int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    v[r].emplace_back(l, i);
  }
  for(int i = 1; i <= n; i++) {
    int l = max(1, i - a[i].e);
    int r = i - a[i].b;
    for(int j : start[i]) {
      add(j);
    }
    if(l <= r) {
      update(l, r, a[i].h);
    }
    for(auto j : v[i]) {
      ans[j.second] = query(j.first, n);
      if(ans[j.second] < 0) ans[j.second] = -1;
    } 
    for(int j : fin[i]) {
      del(j);
    }
    l = i + a[i].b;
    r = max(n, i + a[i].e);
    if(l <= r) {
      start[l].push_back(i);
      fin[r].push_back(i);
    }
  }
  for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'int main()':
antennas.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
antennas.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &a[i].h, &a[i].b, &a[i].e);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
antennas.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~

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