Submission #639161

#	Time	Username	Problem	Language	Result	Execution time	Memory
639161		cadmiumsky	Fire (JOI20_ho_t5)	C++14	100 / 100	806 ms	49516 KiB

ho_t5

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

#define int ll

#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;

const int nmax = 2e5 + 5;

#define lsb(x) (x & -x)
struct AIB {
  int tree[nmax * 2];
  int offset, len;
  void init(int l, int r) {
    offset = -l + 1;
    len = r - l + 1;
    memset(tree, 0, sizeof(tree[0]) * (len + 1));
  }
  
  void upd(int x, int val) {
    x += offset;
    //cerr << "+ " << x << ' ' << val << '\n';
    while(x <= len)
      tree[x] += val,
      x += lsb(x);
  }
  
  int query(int x) {
    x += offset;
    int sum = 0;
    while(x > 0)
      sum += tree[x],
      x -= lsb(x);
    return sum;
  }
  int query(int l, int r) {
    //cerr << l + offset << ' ' << r + offset << '\n';
    return query(r) - query(l - 1);
  }
};

namespace DS {
  AIB offset, firstd, secondd;
  
  namespace Updates {
    vector<tii> upd;
    void push(int x, int val, int l, int r) {
      upd.emplace_back(l, val, x);
      upd.emplace_back(r + 1, -val, x + (r + 1) - l);
    }
    void update(int t, int val, int x) {
      //cerr << "+ " << t << ' ' << val << ' ' << x << '\n';
      int coef = x - t;
      offset.upd(coef, -val * t);
      firstd.upd(coef, val);
      secondd.upd(coef, (-coef) * val);
    }
  }
  
  namespace Queries {
    int side;
    vector<tii> qs;
    void push(int l, int r, int t) {
      qs.emplace_back(t, l, r);
    }
    ll query(int t, int l, int r) {
      auto [right, mid, left] = tii{r, r - t, l - t};
      if(side == 1) { // Orizontal \\ partea superioara
	//cerr << t << ' ' << l << ' ' << r << '\t' << '*' << (t + 1) << '\n';
	return (ll)offset.query(left, mid) + (ll)firstd.query(left, mid) * (t + 1);
      }
      else if(side == -1) {
	if(mid == right) return 0;
	mid++;
	return (ll)offset.query(mid, right) + (ll)secondd.query(mid, right) + (ll)firstd.query(mid, right) * (right + 1);
      }
      else if(side == -2) {
	mid = l;
	return (ll)offset.query(left, mid) + (ll)secondd.query(left, mid) + (ll)firstd.query(left, mid) * mid;
      }
      assert(false);
      return 0;
    }
  }
  using namespace Queries;
  using namespace Updates;
  
  void init(int n) {
    vector<int> ind(qs.size());
    vector<ll> rez(qs.size(), 0);
    
    //side == 1
    Queries::side = 1;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return qs[a] < qs[b]; });
    sort(all(upd));
    int ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] = Queries::query(t, l, r);
    }
    
    
    //for(auto x : rez)
      //cout << x << ' ';
    //cout << '\n';
      
    
    //side == -1
    Queries::side = -1;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return get<2>(qs[a]) < get<2>(qs[b]); });
    sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
    ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] += Queries::query(t, l, r);
    }
    
    //for(auto x : rez)
      //cout << x << ' ';
    //cout << '\n';
    
    //side == -2
    Queries::side = -2;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return get<1>(qs[a]) < get<1>(qs[b]); });
    sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
    ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] -= Queries::query(t, l, r);
    }
    
    for(auto x : rez)
      cout << x << '\n';
      
    return;
  }
  
}

signed main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n);
  for(auto &x : v)
    cin >> x;
  vector<int> poz, rend;
  for(int i = n - 1; i >= 0; i--) {
    DS::Updates::push(i, v[i], 0, 0);
    int boundary = i;
    while(!poz.empty() && v[poz.back()] <= v[i]) {
      DS::Updates::push(poz.back(), v[i] - v[poz.back()], poz.back() - i, rend.back() - i);
      boundary = rend.back();
      poz.pop_back();
      rend.pop_back();
    }
    poz.emplace_back(i);
    rend.emplace_back(boundary);
  }
  
  for(int i = 0, t, l, r; i < q; i++) {
    cin >> t >> l >> r;
    --l;
    --r;
    DS::Queries::push(l, r, t);
  }
  
  DS::init(n);
  return 0;
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message (stderr)

ho_t5.cpp: In function 'll DS::Queries::query(ll, ll, ll)':
ho_t5.cpp:74:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |       auto [right, mid, left] = tii{r, r - t, l - t};
      |            ^
ho_t5.cpp: In function 'void DS::init(ll)':
ho_t5.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:112:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |       while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:113:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |  auto [time, val, poz] = upd[ptr];
      |       ^
ho_t5.cpp:138:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:139:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |       while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:140:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |  auto [time, val, poz] = upd[ptr];
      |       ^
ho_t5.cpp:163:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:164:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |       while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:165:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |  auto [time, val, poz] = upd[ptr];
      |       ^

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80