Submission #1037046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037046	2024-07-27T23:38:35 Z	pera	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	340 ms	139608 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int N = 1e9;
int Q;
struct node{
   node *left , *right;
   int sum = 0 , lz = -1;
   node(int x = 0) : sum(x) , lz(0) , left(NULL) , right(NULL){}
} *root;
void push(node *&u , int l , int r){
   if(u->lz == -1){
      return;
   }
   if(u->left == NULL){
      u->left = new node();
   }
   if(u->right == NULL){
      u->right = new node();
   }
   int m = (l + r) / 2;
   u->left->sum = (m - l + 1) * u->lz;
   u->right->sum = (r - m) * u->lz;
   u->left->lz = u->lz;
   u->right->lz = u->lz;
   u->lz = -1;
}
void upd(node *&u , int l , int r , int L , int R , int x){
   if(l > r || r < L || l > R){
      return;
   }
   if(u == NULL){
      u = new node();
   }
   if(L <= l && r <= R){
      u->sum = x * (r - l + 1);
      u->lz = x;
      return;
   }
   push(u , l , r);
   int m = (l + r) / 2;
   upd(u->left , l , m , L , R , x);
   upd(u->right , m + 1 , r , L , R , x);
   u->sum = 0;
   if(u->left){
      u->sum += u->left->sum;
   }
   if(u->right){
      u->sum += u->right->sum;
   }
}
int get(node *&u , int l , int r , int L , int R){
   if(l > r || r < L || l > R || u == NULL){
      return 0;
   }
   if(L <= l && r <= R){
      return u->sum;
   }
   push(u , l , r);
   int m = (l + r) / 2;
   return get(u->left , l , m , L , R) + get(u->right , m + 1 , r , L , R);
}
int main(){
   int C = 0;
   cin >> Q;
   while(Q--){
      int D , X , Y;
      cin >> D >> X >> Y;
      X += C;
      Y += C;
      if(D == 1){
         C = get(root , 1 , N , X , Y);
         cout << C << " ";
      }else{
         upd(root , 1 , N , X , Y , 1);
      }
   }
}

Compilation message

apple.cpp: In constructor 'node::node(int)':
apple.cpp:7:18: warning: 'node::lz' will be initialized after [-Wreorder]
    7 |    int sum = 0 , lz = -1;
      |                  ^~
apple.cpp:6:10: warning:   'node* node::left' [-Wreorder]
    6 |    node *left , *right;
      |          ^~~~
apple.cpp:8:4: warning:   when initialized here [-Wreorder]
    8 |    node(int x = 0) : sum(x) , lz(0) , left(NULL) , right(NULL){}
      |    ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	15 ms	3544 KB	Output is correct
5	Correct	19 ms	4188 KB	Output is correct
6	Correct	19 ms	3976 KB	Output is correct
7	Correct	19 ms	4188 KB	Output is correct
8	Correct	135 ms	30112 KB	Output is correct
9	Correct	253 ms	52460 KB	Output is correct
10	Correct	260 ms	57680 KB	Output is correct
11	Correct	241 ms	62040 KB	Output is correct
12	Correct	243 ms	63828 KB	Output is correct
13	Correct	235 ms	74324 KB	Output is correct
14	Correct	251 ms	75088 KB	Output is correct
15	Correct	314 ms	135504 KB	Output is correct
16	Correct	324 ms	136364 KB	Output is correct
17	Correct	250 ms	77452 KB	Output is correct
18	Correct	239 ms	77652 KB	Output is correct
19	Correct	340 ms	139608 KB	Output is correct
20	Correct	336 ms	139604 KB	Output is correct