Submission #1207073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207073		Zero_OP	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	482 ms	88132 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;
            assert(id < (int)bit.size());
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

      T query_except(int id){ //except [0..id]
            return query((int)bit.size()-2) - 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))]);
            }
      }

      Us.emplace_back(-1e18);
      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]

      Us.emplace_back(1e18);
      int sz = (int)Us.size();

      /*

      X[L[i]] + U >= X[i] <=> U >= X[i] - X[L[i]]
      X[i] + U <= X[R[i]] <=> U <= X[R[i]] - X[i]

      for every j that U >= X[i] - X[L[i]] : sum X[L[i]] * B[i] + sum B[i] * U
      for every j that U <  X[i] - X[L[i]] : sum X[i] * B[i]
      for every j that U >= X[R[i]] - X[L[i]] : -(sum X[L[i]] * B[i] + sum B[i] * U)

      for every j that U < X[R[i]] - X[i] : sum X[i] * B[i] + sum B[i] * U
      for every j that U >=  X[R[i]] - X[i] : sum X[R[i]] * B[i]
      for every j that U >= X[R[i]] - X[L[i]] : -(sum X[R[i]] * B[i])

      */

      Fenwick<long long, 1> bit1(sz), bit2(sz), bit3(sz), bit4(sz), bit5(sz), bit6(sz), bit7(sz), bit8(sz), bit9(sz);

      long long add = 0;
      for(int i = N; i >= 1; --i){
            for(auto j : lpart[i]){
                  int pos1 = lower_bound(Us.begin(), Us.end(), X[j] - X[L[j]]) - Us.begin();
                  int pos2 = lower_bound(Us.begin(), Us.end(), X[R[j]] - X[L[j]]) - Us.begin();

                  add -= X[j] * B[j];

                  bit1.update(pos1, X[L[j]] * B[j]);
                  bit2.update(pos1, B[j]);
                  bit3.update(pos1, X[j] * B[j]);

                  bit4.update(pos2, X[L[j]] * B[j]);
                  bit5.update(pos2, B[j]);

                  bit9.update(pos2, X[R[j]] * B[j]);
            }

            add += X[i] * B[i];
            int pos = lower_bound(Us.begin(), Us.end(), X[R[i]] - X[i]) - Us.begin();
            bit6.update(pos, X[i] * B[i]);
            bit7.update(pos, B[i]);
            bit8.update(pos, X[R[i]] * B[i]);

            for(auto [id, sign, U] : queries[i]){
                  int pos = upper_bound(Us.begin(), Us.end(), U) - Us.begin() - 1;
                  long long tot = 0;

                  tot -= add + bit1.query(pos) - bit4.query(pos) + (bit2.query(pos) - bit5.query(pos)) * U + bit3.query_except(pos);
                  tot += bit6.query_except(pos) + bit7.query_except(pos) * U + bit8.query(pos) - bit9.query(pos);

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

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

      return 0;
}

/*

4 *

*/

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