oj.uz

Submission #639161

# Submission time Handle Problem Language Result Execution time Memory
639161 2022-09-08T18:39:46 Z cadmiumsky Fire (JOI20_ho_t5) C++14
100 / 100
 806 ms 49516 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 730 ms 42844 KB Output is correct
3 Correct 752 ms 48268 KB Output is correct
4 Correct 728 ms 48496 KB Output is correct
5 Correct 716 ms 49028 KB Output is correct
6 Correct 698 ms 48412 KB Output is correct
7 Correct 696 ms 48896 KB Output is correct
8 Correct 727 ms 49168 KB Output is correct
9 Correct 694 ms 48992 KB Output is correct
10 Correct 687 ms 48176 KB Output is correct
11 Correct 764 ms 49340 KB Output is correct
12 Correct 704 ms 48008 KB Output is correct
13 Correct 705 ms 48744 KB Output is correct
14 Correct 708 ms 48648 KB Output is correct
15 Correct 713 ms 48852 KB Output is correct
16 Correct 716 ms 48456 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 731 ms 41972 KB Output is correct
3 Correct 708 ms 46880 KB Output is correct
4 Correct 745 ms 48368 KB Output is correct
5 Correct 724 ms 47224 KB Output is correct
6 Correct 745 ms 47604 KB Output is correct
7 Correct 711 ms 47756 KB Output is correct
8 Correct 746 ms 47444 KB Output is correct
9 Correct 706 ms 47056 KB Output is correct
10 Correct 707 ms 46676 KB Output is correct
11 Correct 728 ms 48268 KB Output is correct
12 Correct 721 ms 47812 KB Output is correct
13 Correct 717 ms 48096 KB Output is correct
14 Correct 744 ms 47240 KB Output is correct
15 Correct 726 ms 48072 KB Output is correct
16 Correct 731 ms 47692 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 40772 KB Output is correct
2 Correct 607 ms 41092 KB Output is correct
3 Correct 646 ms 41800 KB Output is correct
4 Correct 604 ms 40664 KB Output is correct
5 Correct 608 ms 40812 KB Output is correct
6 Correct 597 ms 41056 KB Output is correct
7 Correct 608 ms 41736 KB Output is correct
8 Correct 613 ms 41476 KB Output is correct
9 Correct 608 ms 40996 KB Output is correct
10 Correct 619 ms 41372 KB Output is correct
11 Correct 618 ms 41092 KB Output is correct
12 Correct 614 ms 41164 KB Output is correct
13 Correct 610 ms 40988 KB Output is correct
14 Correct 622 ms 41092 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 730 ms 42844 KB Output is correct
34 Correct 752 ms 48268 KB Output is correct
35 Correct 728 ms 48496 KB Output is correct
36 Correct 716 ms 49028 KB Output is correct
37 Correct 698 ms 48412 KB Output is correct
38 Correct 696 ms 48896 KB Output is correct
39 Correct 727 ms 49168 KB Output is correct
40 Correct 694 ms 48992 KB Output is correct
41 Correct 687 ms 48176 KB Output is correct
42 Correct 764 ms 49340 KB Output is correct
43 Correct 704 ms 48008 KB Output is correct
44 Correct 705 ms 48744 KB Output is correct
45 Correct 708 ms 48648 KB Output is correct
46 Correct 713 ms 48852 KB Output is correct
47 Correct 716 ms 48456 KB Output is correct
48 Correct 731 ms 41972 KB Output is correct
49 Correct 708 ms 46880 KB Output is correct
50 Correct 745 ms 48368 KB Output is correct
51 Correct 724 ms 47224 KB Output is correct
52 Correct 745 ms 47604 KB Output is correct
53 Correct 711 ms 47756 KB Output is correct
54 Correct 746 ms 47444 KB Output is correct
55 Correct 706 ms 47056 KB Output is correct
56 Correct 707 ms 46676 KB Output is correct
57 Correct 728 ms 48268 KB Output is correct
58 Correct 721 ms 47812 KB Output is correct
59 Correct 717 ms 48096 KB Output is correct
60 Correct 744 ms 47240 KB Output is correct
61 Correct 726 ms 48072 KB Output is correct
62 Correct 731 ms 47692 KB Output is correct
63 Correct 625 ms 40772 KB Output is correct
64 Correct 607 ms 41092 KB Output is correct
65 Correct 646 ms 41800 KB Output is correct
66 Correct 604 ms 40664 KB Output is correct
67 Correct 608 ms 40812 KB Output is correct
68 Correct 597 ms 41056 KB Output is correct
69 Correct 608 ms 41736 KB Output is correct
70 Correct 613 ms 41476 KB Output is correct
71 Correct 608 ms 40996 KB Output is correct
72 Correct 619 ms 41372 KB Output is correct
73 Correct 618 ms 41092 KB Output is correct
74 Correct 614 ms 41164 KB Output is correct
75 Correct 610 ms 40988 KB Output is correct
76 Correct 622 ms 41092 KB Output is correct
77 Correct 713 ms 48440 KB Output is correct
78 Correct 715 ms 49024 KB Output is correct
79 Correct 727 ms 48944 KB Output is correct
80 Correct 711 ms 48324 KB Output is correct
81 Correct 706 ms 48124 KB Output is correct
82 Correct 729 ms 48672 KB Output is correct
83 Correct 712 ms 48468 KB Output is correct
84 Correct 776 ms 48108 KB Output is correct
85 Correct 805 ms 48888 KB Output is correct
86 Correct 806 ms 48324 KB Output is correct
87 Correct 718 ms 49300 KB Output is correct
88 Correct 727 ms 49200 KB Output is correct
89 Correct 684 ms 47996 KB Output is correct
90 Correct 706 ms 48924 KB Output is correct
91 Correct 689 ms 48312 KB Output is correct
92 Correct 688 ms 47844 KB Output is correct
93 Correct 702 ms 48556 KB Output is correct
94 Correct 716 ms 49516 KB Output is correct
95 Correct 734 ms 49368 KB Output is correct
96 Correct 692 ms 48572 KB Output is correct
97 Correct 693 ms 48584 KB Output is correct
98 Correct 670 ms 47848 KB Output is correct
99 Correct 701 ms 48204 KB Output is correct
100 Correct 693 ms 48532 KB Output is correct
101 Correct 682 ms 48080 KB Output is correct
102 Correct 711 ms 48956 KB Output is correct