제출 #1198886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198886		codeshit	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	4094 ms	72800 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

const int MAX = 2e5 + 5;

int N, Q, A[MAX], B[MAX], L[MAX], R[MAX], rmq[20][MAX], idx[20][MAX];
long long X[MAX], ans[MAX];
vector<int> lpart[MAX];
vector<tuple<int, int, int>> queries[MAX];

int f(int i, int j){
      return B[i] < B[j] ? i : (B[i] > B[j] ? j : min(i, j));
}

int get_max(int l, int r){
      int k = 31 - __builtin_clz(r - l + 1);
      return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int get_f(int l, int r){
      int k = 31 - __builtin_clz(r - l + 1);
      return f(idx[k][l], idx[k][r - (1 << k) + 1]);
}

//struct SegmentTree{
//      vector<int> cnt;
//      vector<long long> sum;
//      SegmentTree(int n) : cnt(n << 2), sum(n << 2) {}
//
//      void update(int id, int l, int r, int pos, int vcnt, long long vsum){
//            if(l == r) cnt[id] += vcnt, sum[id] += vsum;
//            else{
//                  int mid = l + r >> 1;
//                  if(pos <= mid) update(id << 1, l, mid, pos, vcnt, vsum);
//                  else update(id << 1 | 1, mid + 1, r, vcnt, vsum);
//                  cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
//                  sum[id] = sum[id << 1] + sum[id << 1 | 1];
//            }
//      }
//
//      pair<int, long long> query(int id, int l, int r, int u, int v){
//            if(u <= l && r <= v){
//                  return make_pair(cnt[id], sum[id]);
//            } else{
//                  int mid = l + r >> 1;
//                  int vcnt = 0; long long vsum = 0;
//                  if(u <= mid){
//                        int ncnt, nsum;
//                        tie(ncnt, nsum) = query(id << 1, l, mid, u, v);
//                        vcnt += ncnt;
//                        vsum += nsum;
//                  }
//
//                  if(mid < v){
//                        int ncnt, nsum;
//                        tie(ncnt, nsum) = query(id << 1 | 1, mid+1, r, u, v);
//                        vcnt += ncnt;
//                        vsum += nsum;
//                  }
//
//                  return make_pair(vcnt, vsum);
//            }
//      }
//};

template<typename T, int offset = 1>
struct Fenwick{
      vector<T> bit;
      Fenwick(int n) : bit(n + 1, 0) {}

      void update(int id, T val){
            id += offset;
            for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val;
      }

      T query(int id){
            id += offset;
            T sum = 0;
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

      T query_except(int id){ //except [0..id]
            return query((int)bit.size()-1) - query(id);
      }
};

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL

      cin >> N >> Q;
      for(int i = 1; i <= N; ++i) cin >> A[i];
      for(int i = 1; i <= N; ++i) cin >> B[i], rmq[0][i] = A[i], idx[0][i] = i;

      X[0] = -1e9;
      for(int i = 2; i <= N+1; ++i) X[i] = X[i-1] + A[i-1];

      vector<long long> Us;
      vector<int> st = {0};
      for(int i = 1; i <= N; ++i){
            while(!st.empty() && B[st.back()] > B[i]) st.pop_back();
            assert(!st.empty());
            L[i] = st.back();
            st.push_back(i);
            Us.emplace_back(X[i] - X[L[i]]);
            lpart[L[i]].emplace_back(i);
      }

      st = {N+1};
      for(int i = N; i >= 1; --i){
            while(!st.empty()  && B[st.back()] >= B[i]) st.pop_back();
            assert(!st.empty());
            R[i] = st.back();
            st.push_back(i);
            Us.emplace_back(X[R[i]] - X[i]);
            Us.emplace_back(X[R[i]] - X[L[i]]);
      }

      for(int i = 1; (1 << i) <= N; ++i){
            for(int j = 1; j + (1 << i) - 1 <= N; ++j){
                  rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
                  idx[i][j] = f(idx[i-1][j], idx[i-1][j + (1 << (i-1))]);
            }
      }


      sort(Us.begin(), Us.end()); Us.erase(unique(Us.begin(), Us.end()), Us.end());

      for(int i = 0; i < Q; ++i){
            int S, T, U;
            cin >> S >> T >> U;

            if(get_max(S, T-1) > U){
                  ans[i] = -1;
                  continue;
            }

            int pos = lower_bound(X, X + N+2, max(X[T] - U, X[S])) - X;
            int last = get_f(pos, T-1);

            ans[i] += 1LL * (X[T] - X[last]) * B[last];
//            cout << dbg(ans[i]) << '\n';
            if(S != last){
                  queries[S].emplace_back(i, +1, U);
                  queries[last].emplace_back(i, -1, U);
            }
      }



      //maxU : - max(X[i], X[L[i]] + U) * B[i]
      //minU : + min(X[R[i]], X[i] + U) * B[i]

      //subtract tree
      Us.emplace_back(1e18);
      int sz = (int)Us.size();
      Fenwick<int, 1> count1(sz), count2(sz);
      Fenwick<long long, 1> sum1(sz), sum2(sz), sum3(sz), sum4(sz), sum5(sz), sum6(sz);

//      for(int i = 1; i <= N; ++i) cout << L[i] << ' ' << R[i] << '\n';
      for(int i = N; i >= 1; --i){
//            for(auto j : lpart[i]){
//                  assert(L[j] == i);
//
//                  int cur = lower_bound(Us.begin(), Us.end(), X[j] - X[i]) - Us.begin();
//                  int stop =  lower_bound(Us.begin(), Us.end(), X[R[j]] - X[i]) - Us.begin();
//                  count1.update(cur, +1);
//                  count1.update(stop, -1);
//                  sum1.update(cur, X[L[j]] * B[i]);
//                  sum1.update(stop, X[L[j]] * B[i]);
//                  sum2.update(cur, B[i]);
//                  sum2.update(stop, -B[i]);
//                  sum3.update(cur, X[i] * B[i]);
//            }
//
//            int stop = lower_bound(Us.begin(), Us.end(), X[R[i]] - X[i]) - Us.begin();
//            count2.update(stop, +1);
//            sum4.update(stop, X[R[i]] * B[i]);
//            sum5.update(stop, B[i]);
//            sum6.update(stop, X[i] * B[i]);
//
//            for(auto [id, sign, U] : queries[i]){
//                  long long tot = 0;
//
//                  int pu = upper_bound(Us.begin(), Us.end(), U) - Us.begin() - 1;
//                  int cnt = count1.query(pu);
//                  long long sumBase = sum1.query(pu);
//                  long long sumB = sum2.query(pu);
//                  tot -= sumBase + 1LL * sumB * U * cnt + sum3.query_except(pu);
//
//                  cnt = count2.query_except(pu);
//                  sumBase = sum4.query(pu);
//                  sumB = sum5.query_except(pu);
//                  tot += sumBase + 1LL * sumB * U * cnt + sum6.query(pu);
//
//                  cout << dbg(tot) << dbg(sign) << '\n';
//                  ans[id] += sign * tot;
//            }

            for(auto [id, sign, U] : queries[i]){
                  long long tot = 0;
                  for(int j = i; j <= N; ++j){
                        int r = min(X[R[j]], X[j] + U);
                        int l = (L[j] >= i ? max(X[L[j]] + U, X[j]) : X[j]);
//                        cout << dbg(l) << dbg(r) << '\n';
                        tot += 1LL * B[j] * max(0, (r - l));
                  }

                  ans[id] += sign * tot;
//                  cout << dbg(sign) << dbg(tot) << '\n';
            }
      }

      for(int i = 0; i < Q; ++i) cout << ans[i] << '\n';

      return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44