QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708525#3850. DJ Darkoahsoltan#RE 0ms0kbC++203.9kb2024-11-03 23:10:482024-11-03 23:11:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 23:11:00]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-03 23:10:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}";
}
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")";
}
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

struct se {
  struct node{
    ll mn, mx;
    ll push_set, push_add;
    ll su;
  };

  vector<node> st;
  int si;


  void tag_set(int p, ll v) {
      st[p].mn = st[p].mx = st[p].push_set = v;
      st[p].push_add = 0;
  }

  void tag_add(int p, ll v) {
      st[p].mn += v;
      st[p].mx += v;
      if(st[p].push_set != -1)
        st[p].push_set += v;
      else 
        st[p].push_add += v;
  }


  void push(int p) {
    assert(st[p].push_set == -1 || st[p].push_add == 0);
    if(st[p].push_set != -1) {    
      tag_set(2 * p, st[p].push_set);
      tag_set(2 * p + 1, st[p].push_set);
      st[p].push_set = -1;
    }
    if(st[p].push_add) {
      tag_add(2 * p, st[p].push_add);
      tag_add(2 * p + 1, st[p].push_add);      
      st[p].push_add = 0;
    }
  }

  void upd(int p) {
    st[p].mn = min(st[2 * p].mn, st[2 * p + 1].mn);
    st[p].mx = max(st[2 * p].mx, st[2 * p + 1].mx);
  }

  void build(vector<ll> co) {
    si = 1;
    while(si <= 2 * sz(co) + 2)
      si *= 2;
    st.assign(si, node{-1, -1, -1, 0LL, 0LL});
    rep(i, 0, sz(co))
      st[i + si / 2].su = co[i];
    for(int i = si / 2 - 1; i >= 1; --i) {
      st[i].su = st[2 *i].su + st[2 * i + 1].su;
    }
  }

  void add(int b, int e, int x, int y, int p, ll v) {
    if(e < x || b > y)
      return;
    if(x <= b && e <= y) {
      tag_add(p, v);
      return;
    }
    push(p);
    int mid = (b + e) / 2;
    add(b, mid, x, y, 2 * p, v);
    add(mid + 1, e, x, y, 2 * p + 1, v);
    upd(p);
  }



  void set(int b, int e, int x, int y, int p, ll v) {
    if(e < x || b > y)
      return;
    if(x <= b && e <= y) {
      tag_set(p, v);
      return;
    }
    push(p);
    int mid = (b + e) / 2;
    set(b, mid, x, y, 2 * p, v);
    set(mid + 1, e, x, y, 2 * p + 1, v);
    upd(p);
  }

  vector<pair<ll, ll>> vr;

  void ge(int b, int e, int x, int y, int p) {
    if(e < x || b > y)
      return;
    if(x <= b && e <= y && st[p].mx == st[p].mn) {
      vr.emplace_back(st[p].mx, st[p].su);
      return;
    }
    push(p);
    int mid = (b + e) / 2;
    ge(b, mid, x, y, 2 * p);
    ge(mid + 1, e, x, y, 2 * p + 1);
    upd(p);
  }

  void ose(int b, int e, ll v) {
    set(1, si / 2, b, e, 1, v);
  }

  void oadd(int b, int e, ll v) {
    add(1, si / 2, b, e, 1, v);
  }

  vector<pair<ll, ll>> oge(int b, int e) {
    vr.clear();
    ge(1, si / 2, b, e, 1);
    return vr;
  }

};


ll daj(vector<pair<ll, ll>> ve) {

  sort(all(ve));

  ll left = 0;
  ll right = 0;

  for(auto [itr, co] : ve) {
    right -= co;  
  }  

  for(auto [itr, co] : ve) {
    right += co;

    if(right + co >= 0 && left + co >= 0)
      return itr;
    
    left -= co;
  }

  assert(false);
}


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

  int n, q;
  cin >> n >> q;
  vector<ll> cur(n);
  vector<ll> cost(n);

  for(auto &i : cur)
    cin >> i;

  for(auto &i : cost)
    cin >> i;

  se st;

  st.build(cost);

  for(int i = 0; i < n; i++)
    st.ose(i + 1, i + 1, cur[i]);

  
  rep(_, 0, q) {
    int tp;
    cin >> tp;
    if(tp == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      st.oadd(l, r, x);
    }
    else {
      int l, r;
      cin >> l >> r;
      auto tmp = st.oge(l, r);

      int nowy = daj(tmp);
      cout << nowy << endl;

      st.ose(l, r, nowy);
    }
  }


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

200000 200000
185413631 745038744 881479208 394948467 101727403 796960399 284541402 80768155 286582974 546327406 197495962 552359542 727479505 437895671 143092948 7626834 741609268 540494577 298656274 548860413 41137417 210529949 658779847 161355446 486548926 602900245 119414972 310187428 238177860 ...

output:


result: