oj.uz

Submission #966272

# Submission time Handle Problem Language Result Execution time Memory
966272 2024-04-19T16:01:55 Z huutuan Fish 2 (JOI22_fish2) C++14
100 / 100
 672 ms 69612 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Range{
   int sum;
   int cnt;
   int block;
   Range (int _sum=0, int _cnt=0, int _block=0){
      sum=_sum, cnt=_cnt, block=_block;
   }
};

const int N=1e5+10, LG=32, inf=1e18;
vector<Range> pf_q1, pf_q2, sf_q1, sf_q2;

struct Node{
   vector<Range> pf, sf;
   int cnt;
   int sum;
   int l, r, lval, rval;
   Node (){
      pf.reserve(LG);
      sf.reserve(LG);
      cnt=sum=0;
      l=1, r=0;
   }
   void merge(Node &tl, Node &tr){
      pf=tl.pf;
      sf=tr.sf;
      pf.pop_back();
      sf.pop_back();
      if (tl.sum==0){
         (*this)=tr;
         return;
      }
      if (tr.sum==0){
         (*this)=tl;
         return;
      }
      l=tl.l, r=tr.r, lval=tl.lval, rval=tr.rval;
      sum=tl.sum+tr.sum;
      cnt=0;
      pf_q1.clear();
      pf_q2.clear();
      sf_q1.clear();
      sf_q2.clear();
      for (int _i=1, j=0; _i<=(int)tl.sf.size(); ++_i){
         int i=_i;
         int curl=(i?tl.sf[i-1].sum:0);
         int curr=(j?tr.pf[j-1].sum:0);
         int cur;
         int _block=0;
         while (1){
            bool stop=true;
            while (j<(int)tr.pf.size()){
               cur=curl+curr;
               int block=j?tr.pf[j-1].block:tr.lval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curr=tr.pf[j++].sum;
            }
            while (i<(int)tl.sf.size()){
               cur=curl+curr;
               int block=i?tl.sf[i-1].block:tl.rval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curl=tl.sf[i++].sum;
            }
            if (stop) break;
         }
         if (i==(int)tl.sf.size() && j==(int)tr.pf.size()){
            cnt+=tl.sf[_i-1].cnt;
         }else if (i==(int)tl.sf.size()){
            pf_q1.emplace_back(cur, tl.sf[_i-1].cnt, _block);
         }else if (j==(int)tr.pf.size()){
            sf_q1.emplace_back(cur, tl.sf[_i-1].cnt, _block);
         }
      }
      for (int _j=1, i=0; _j<=(int)tr.pf.size(); ++_j){
         int j=_j;
         int curl=(i?tl.sf[i-1].sum:0);
         int curr=(j?tr.pf[j-1].sum:0);
         int cur;
         int _block=0;
         while (1){
            bool stop=true;
            while (j<(int)tr.pf.size()){
               cur=curl+curr;
               int block=j?tr.pf[j-1].block:tr.lval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curr=tr.pf[j++].sum;
            }
            while (i<(int)tl.sf.size()){
               cur=curl+curr;
               int block=i?tl.sf[i-1].block:tl.rval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curl=tl.sf[i++].sum;
            }
            if (stop) break;
         }
         if (i==(int)tl.sf.size() && j==(int)tr.pf.size()){
            cnt+=tr.pf[_j-1].cnt;
         }else if (i==(int)tl.sf.size()){
            pf_q2.emplace_back(cur, tr.pf[_j-1].cnt, _block);
         }else if (j==(int)tr.pf.size()){
            sf_q2.emplace_back(cur, tr.pf[_j-1].cnt, _block);
         }
      }
      int i1=0, i2=0;
      while (i1<(int)pf_q1.size() && i2<(int)pf_q2.size()){
         if (pf_q1[i1].sum<=pf_q2[i2].sum){
            if (pf.size() && pf.back().sum==pf_q1[i1].sum) pf.back().cnt+=pf_q1[i1].cnt;
            else pf.push_back(pf_q1[i1]);
            ++i1;
         }else{
            if (pf.size() && pf.back().sum==pf_q2[i2].sum) pf.back().cnt+=pf_q2[i2].cnt;
            else pf.push_back(pf_q2[i2]);
            ++i2;
         }
      }
      while (i1<(int)pf_q1.size()){
         if (pf.size() && pf.back().sum==pf_q1[i1].sum) pf.back().cnt+=pf_q1[i1].cnt;
         else pf.push_back(pf_q1[i1]);
         ++i1;
      }
      while (i2<(int)pf_q2.size()){
         if (pf.size() && pf.back().sum==pf_q2[i2].sum) pf.back().cnt+=pf_q2[i2].cnt;
         else pf.push_back(pf_q2[i2]);
         ++i2;
      }
      i1=0, i2=0;
      while (i1<(int)sf_q1.size() && i2<(int)sf_q2.size()){
         if (sf_q1[i1].sum<=sf_q2[i2].sum){
            if (sf.size() && sf.back().sum==sf_q1[i1].sum) sf.back().cnt+=sf_q1[i1].cnt;
            else sf.push_back(sf_q1[i1]);
            ++i1;
         }else{
            if (sf.size() && sf.back().sum==sf_q2[i2].sum) sf.back().cnt+=sf_q2[i2].cnt;
            else sf.push_back(sf_q2[i2]);
            ++i2;
         }
      }
      while (i1<(int)sf_q1.size()){
         if (sf.size() && sf.back().sum==sf_q1[i1].sum) sf.back().cnt+=sf_q1[i1].cnt;
         else sf.push_back(sf_q1[i1]);
         ++i1;
      }
      while (i2<(int)sf_q2.size()){
         if (sf.size() && sf.back().sum==sf_q2[i2].sum) sf.back().cnt+=sf_q2[i2].cnt;
         else sf.push_back(sf_q2[i2]);
         ++i2;
      }
      pf.emplace_back(sum, cnt, inf);
      sf.emplace_back(sum, cnt, inf);
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, int *a){
      if (l==r){
         t[k].cnt=1;
         t[k].sum=a[l];
         t[k].l=t[k].r=l;
         t[k].lval=t[k].rval=a[l];
         t[k].pf.clear();
         t[k].sf.clear();
         t[k].pf.emplace_back(a[l], 1, inf);
         t[k].sf.emplace_back(a[l], 1, inf);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k].cnt=1;
         t[k].sum=t[k].lval=t[k].rval=val;
         t[k].pf.clear();
         t[k].sf.clear();
         t[k].pf.emplace_back(val, 1, inf);
         t[k].sf.emplace_back(val, 1, inf);
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   Node ans, ans2;
   void get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         ans.merge(ans2, t[k]);
         ans2=ans;
         return;
      }
      int mid=(l+r)>>1;
      get(k<<1, l, mid, L, R);
      get(k<<1|1, mid+1, r, L, R);
   }
} st;

int n, q, a[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i];
   st.init(n);
   st.build(1, 1, n, a);
   cin >> q;
   while (q--){
      int type; cin >> type;
      if (type==1){
         int x, y; cin >> x >> y;
         st.update(1, 1, n, x, y);
      }else{
         int l, r; cin >> l >> r;
         st.ans=Node(); st.ans2=Node();
         st.get(1, 1, n, l, r);
         cout << st.ans.cnt << '\n';
      }
   }
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 64 ms 62804 KB Output is correct
3 Correct 62 ms 61524 KB Output is correct
4 Correct 59 ms 62668 KB Output is correct
5 Correct 58 ms 61588 KB Output is correct
6 Correct 51 ms 56028 KB Output is correct
7 Correct 51 ms 55376 KB Output is correct
8 Correct 54 ms 56148 KB Output is correct
9 Correct 49 ms 55380 KB Output is correct
10 Correct 62 ms 63560 KB Output is correct
11 Correct 57 ms 59728 KB Output is correct
12 Correct 52 ms 55124 KB Output is correct
13 Correct 51 ms 55120 KB Output is correct
14 Correct 52 ms 56916 KB Output is correct
15 Correct 57 ms 57296 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 64 ms 62804 KB Output is correct
23 Correct 62 ms 61524 KB Output is correct
24 Correct 59 ms 62668 KB Output is correct
25 Correct 58 ms 61588 KB Output is correct
26 Correct 51 ms 56028 KB Output is correct
27 Correct 51 ms 55376 KB Output is correct
28 Correct 54 ms 56148 KB Output is correct
29 Correct 49 ms 55380 KB Output is correct
30 Correct 62 ms 63560 KB Output is correct
31 Correct 57 ms 59728 KB Output is correct
32 Correct 52 ms 55124 KB Output is correct
33 Correct 51 ms 55120 KB Output is correct
34 Correct 52 ms 56916 KB Output is correct
35 Correct 57 ms 57296 KB Output is correct
36 Correct 66 ms 63160 KB Output is correct
37 Correct 66 ms 61520 KB Output is correct
38 Correct 70 ms 61268 KB Output is correct
39 Correct 84 ms 63012 KB Output is correct
40 Correct 66 ms 61252 KB Output is correct
41 Correct 55 ms 56228 KB Output is correct
42 Correct 60 ms 56040 KB Output is correct
43 Correct 60 ms 55636 KB Output is correct
44 Correct 65 ms 55688 KB Output is correct
45 Correct 67 ms 63572 KB Output is correct
46 Correct 80 ms 63644 KB Output is correct
47 Correct 61 ms 58716 KB Output is correct
48 Correct 51 ms 55412 KB Output is correct
49 Correct 50 ms 55124 KB Output is correct
50 Correct 56 ms 56916 KB Output is correct
51 Correct 65 ms 57156 KB Output is correct
52 Correct 58 ms 56912 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 64 ms 62804 KB Output is correct
3 Correct 62 ms 61524 KB Output is correct
4 Correct 59 ms 62668 KB Output is correct
5 Correct 58 ms 61588 KB Output is correct
6 Correct 51 ms 56028 KB Output is correct
7 Correct 51 ms 55376 KB Output is correct
8 Correct 54 ms 56148 KB Output is correct
9 Correct 49 ms 55380 KB Output is correct
10 Correct 62 ms 63560 KB Output is correct
11 Correct 57 ms 59728 KB Output is correct
12 Correct 52 ms 55124 KB Output is correct
13 Correct 51 ms 55120 KB Output is correct
14 Correct 52 ms 56916 KB Output is correct
15 Correct 57 ms 57296 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 553 ms 63228 KB Output is correct
18 Correct 473 ms 64892 KB Output is correct
19 Correct 534 ms 63060 KB Output is correct
20 Correct 554 ms 62952 KB Output is correct
21 Correct 555 ms 62932 KB Output is correct
22 Correct 454 ms 64596 KB Output is correct
23 Correct 545 ms 62800 KB Output is correct
24 Correct 573 ms 62988 KB Output is correct
25 Correct 544 ms 63312 KB Output is correct
26 Correct 551 ms 63060 KB Output is correct
27 Correct 310 ms 58020 KB Output is correct
28 Correct 321 ms 57948 KB Output is correct
29 Correct 356 ms 58152 KB Output is correct
30 Correct 460 ms 56976 KB Output is correct
31 Correct 459 ms 57168 KB Output is correct
32 Correct 614 ms 61116 KB Output is correct
33 Correct 666 ms 65636 KB Output is correct
34 Correct 595 ms 60756 KB Output is correct
35 Correct 601 ms 59972 KB Output is correct
36 Correct 672 ms 65656 KB Output is correct
37 Correct 310 ms 57280 KB Output is correct
38 Correct 293 ms 56720 KB Output is correct
39 Correct 364 ms 58960 KB Output is correct
40 Correct 309 ms 59216 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 64 ms 62804 KB Output is correct
3 Correct 62 ms 61524 KB Output is correct
4 Correct 59 ms 62668 KB Output is correct
5 Correct 58 ms 61588 KB Output is correct
6 Correct 51 ms 56028 KB Output is correct
7 Correct 51 ms 55376 KB Output is correct
8 Correct 54 ms 56148 KB Output is correct
9 Correct 49 ms 55380 KB Output is correct
10 Correct 62 ms 63560 KB Output is correct
11 Correct 57 ms 59728 KB Output is correct
12 Correct 52 ms 55124 KB Output is correct
13 Correct 51 ms 55120 KB Output is correct
14 Correct 52 ms 56916 KB Output is correct
15 Correct 57 ms 57296 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 388 ms 65708 KB Output is correct
18 Correct 395 ms 68612 KB Output is correct
19 Correct 308 ms 62696 KB Output is correct
20 Correct 271 ms 67912 KB Output is correct
21 Correct 401 ms 65656 KB Output is correct
22 Correct 352 ms 68688 KB Output is correct
23 Correct 380 ms 62944 KB Output is correct
24 Correct 343 ms 68480 KB Output is correct
25 Correct 344 ms 62620 KB Output is correct
26 Correct 194 ms 60244 KB Output is correct
27 Correct 246 ms 60788 KB Output is correct
28 Correct 267 ms 62780 KB Output is correct
29 Correct 266 ms 60388 KB Output is correct
30 Correct 269 ms 61012 KB Output is correct
31 Correct 297 ms 63492 KB Output is correct
32 Correct 367 ms 67520 KB Output is correct
33 Correct 377 ms 60872 KB Output is correct
34 Correct 323 ms 69468 KB Output is correct
35 Correct 343 ms 65104 KB Output is correct
36 Correct 317 ms 66388 KB Output is correct
37 Correct 277 ms 61776 KB Output is correct
38 Correct 210 ms 60688 KB Output is correct
39 Correct 227 ms 61420 KB Output is correct
40 Correct 137 ms 60496 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 64 ms 62804 KB Output is correct
23 Correct 62 ms 61524 KB Output is correct
24 Correct 59 ms 62668 KB Output is correct
25 Correct 58 ms 61588 KB Output is correct
26 Correct 51 ms 56028 KB Output is correct
27 Correct 51 ms 55376 KB Output is correct
28 Correct 54 ms 56148 KB Output is correct
29 Correct 49 ms 55380 KB Output is correct
30 Correct 62 ms 63560 KB Output is correct
31 Correct 57 ms 59728 KB Output is correct
32 Correct 52 ms 55124 KB Output is correct
33 Correct 51 ms 55120 KB Output is correct
34 Correct 52 ms 56916 KB Output is correct
35 Correct 57 ms 57296 KB Output is correct
36 Correct 66 ms 63160 KB Output is correct
37 Correct 66 ms 61520 KB Output is correct
38 Correct 70 ms 61268 KB Output is correct
39 Correct 84 ms 63012 KB Output is correct
40 Correct 66 ms 61252 KB Output is correct
41 Correct 55 ms 56228 KB Output is correct
42 Correct 60 ms 56040 KB Output is correct
43 Correct 60 ms 55636 KB Output is correct
44 Correct 65 ms 55688 KB Output is correct
45 Correct 67 ms 63572 KB Output is correct
46 Correct 80 ms 63644 KB Output is correct
47 Correct 61 ms 58716 KB Output is correct
48 Correct 51 ms 55412 KB Output is correct
49 Correct 50 ms 55124 KB Output is correct
50 Correct 56 ms 56916 KB Output is correct
51 Correct 65 ms 57156 KB Output is correct
52 Correct 58 ms 56912 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 553 ms 63228 KB Output is correct
55 Correct 473 ms 64892 KB Output is correct
56 Correct 534 ms 63060 KB Output is correct
57 Correct 554 ms 62952 KB Output is correct
58 Correct 555 ms 62932 KB Output is correct
59 Correct 454 ms 64596 KB Output is correct
60 Correct 545 ms 62800 KB Output is correct
61 Correct 573 ms 62988 KB Output is correct
62 Correct 544 ms 63312 KB Output is correct
63 Correct 551 ms 63060 KB Output is correct
64 Correct 310 ms 58020 KB Output is correct
65 Correct 321 ms 57948 KB Output is correct
66 Correct 356 ms 58152 KB Output is correct
67 Correct 460 ms 56976 KB Output is correct
68 Correct 459 ms 57168 KB Output is correct
69 Correct 614 ms 61116 KB Output is correct
70 Correct 666 ms 65636 KB Output is correct
71 Correct 595 ms 60756 KB Output is correct
72 Correct 601 ms 59972 KB Output is correct
73 Correct 672 ms 65656 KB Output is correct
74 Correct 310 ms 57280 KB Output is correct
75 Correct 293 ms 56720 KB Output is correct
76 Correct 364 ms 58960 KB Output is correct
77 Correct 309 ms 59216 KB Output is correct
78 Correct 1 ms 344 KB Output is correct
79 Correct 388 ms 65708 KB Output is correct
80 Correct 395 ms 68612 KB Output is correct
81 Correct 308 ms 62696 KB Output is correct
82 Correct 271 ms 67912 KB Output is correct
83 Correct 401 ms 65656 KB Output is correct
84 Correct 352 ms 68688 KB Output is correct
85 Correct 380 ms 62944 KB Output is correct
86 Correct 343 ms 68480 KB Output is correct
87 Correct 344 ms 62620 KB Output is correct
88 Correct 194 ms 60244 KB Output is correct
89 Correct 246 ms 60788 KB Output is correct
90 Correct 267 ms 62780 KB Output is correct
91 Correct 266 ms 60388 KB Output is correct
92 Correct 269 ms 61012 KB Output is correct
93 Correct 297 ms 63492 KB Output is correct
94 Correct 367 ms 67520 KB Output is correct
95 Correct 377 ms 60872 KB Output is correct
96 Correct 323 ms 69468 KB Output is correct
97 Correct 343 ms 65104 KB Output is correct
98 Correct 317 ms 66388 KB Output is correct
99 Correct 277 ms 61776 KB Output is correct
100 Correct 210 ms 60688 KB Output is correct
101 Correct 227 ms 61420 KB Output is correct
102 Correct 137 ms 60496 KB Output is correct
103 Correct 480 ms 62768 KB Output is correct
104 Correct 373 ms 69448 KB Output is correct
105 Correct 544 ms 63244 KB Output is correct
106 Correct 468 ms 65104 KB Output is correct
107 Correct 468 ms 62800 KB Output is correct
108 Correct 394 ms 69612 KB Output is correct
109 Correct 598 ms 63652 KB Output is correct
110 Correct 458 ms 66632 KB Output is correct
111 Correct 552 ms 63548 KB Output is correct
112 Correct 528 ms 65420 KB Output is correct
113 Correct 278 ms 60552 KB Output is correct
114 Correct 307 ms 58420 KB Output is correct
115 Correct 440 ms 63488 KB Output is correct
116 Correct 417 ms 62428 KB Output is correct
117 Correct 307 ms 59000 KB Output is correct
118 Correct 486 ms 59712 KB Output is correct
119 Correct 317 ms 60968 KB Output is correct
120 Correct 397 ms 63160 KB Output is correct
121 Correct 411 ms 61520 KB Output is correct
122 Correct 401 ms 67652 KB Output is correct
123 Correct 544 ms 61120 KB Output is correct
124 Correct 492 ms 63396 KB Output is correct
125 Correct 528 ms 59476 KB Output is correct
126 Correct 533 ms 62752 KB Output is correct
127 Correct 361 ms 61784 KB Output is correct
128 Correct 332 ms 58488 KB Output is correct
129 Correct 333 ms 61620 KB Output is correct
130 Correct 324 ms 60412 KB Output is correct