Submission #526268

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526268	2022-02-14T06:22:06 Z	tmn2005	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	333 ms	157436 KB

apple

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ar array

#define vec vector
#define ret return

#define ins insert
#define mk make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front

#define pii pair<int,int>

#define all(s) s.begin(), s.end()
#define allr(s) s.rbegin(), s.rend()

#define NeedForSpeed ios::sync_with_stdio(0),cin.tie(0);
const int N = 1e7+12,INF = 1e9,mod = 1e9+7;
const int dx[4] = {1, 0,-1, 0}, dy[4] = {0, 1, 0,-1};
bool iswowel(char n){ n = toupper(n); if(n == 'A' || n == 'O' || n == 'U' || n == 'E' || n == 'I') return true; else return false;}
int n, m, k, x, y, l, r, o, timer=1, ans, res, ok, mx, mn = INF;
int a, b, c;
struct dat{
	int fr, sc, sum, lz;
	dat(){
		fr = sc = sum = lz = 0;
	}
} t[N];

void push(int v, int d){
	if(!t[v].lz)ret;
	
	if(!t[v].fr)t[v].fr = ++timer;
	if(!t[v].sc)t[v].sc = ++timer;
		
	t[v].sum = d;
	t[t[v].fr].lz = 1;
	t[t[v].sc].lz = 1;
			
	t[v].lz = 0;
}
int get(int v, int l, int r, int ql, int qr){
	push(v, r - l + 1);
	if(r < ql || qr < l)
		ret 0;
	if(ql <= l && r <= qr)
		ret t[v].sum;
	int m = l + r >> 1;
	ret(get(t[v].fr, l, m, ql, qr) + get(t[v].sc, m+1, r, ql, qr));
}
void update(int v, int l, int r, int ql, int qr){
	push(v, r - l + 1);
	if(r < ql || qr < l)
		ret;
	if(ql <= l && r <= qr){
		t[v].lz = 1;
		push(v, r - l + 1);
	}
	else{	
		int m = l + r >> 1;
		
		if(!t[v].fr)t[v].fr = ++timer;
		if(!t[v].sc)t[v].sc = ++timer;
		
 		update(t[v].fr, l, m, ql, qr);
		update(t[v].sc, m+1, r, ql, qr);
		
		t[v].sum = t[t[v].fr].sum + t[t[v].sc].sum;
	}
}
main(){
	NeedForSpeed
    cin>>n;
    for(int i=1; i<=n; i++){
    	cin>>o>>l>>r;
    	if(o == 1){
    		int tmp = get(1, 1, INF, l+c, r+c);
    		cout<<tmp<<"\n";
    		c = tmp;
		}
		else{
			update(1, 1, INF, l+c, r+c);
		}
	}




	return 0;
}

Compilation message

apple.cpp: In function 'int get(int, int, int, int, int)':
apple.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int m = l + r >> 1;
      |          ~~^~~
apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int m = l + r >> 1;
      |           ~~^~~
apple.cpp: At global scope:
apple.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	156740 KB	Output is correct
2	Correct	66 ms	156728 KB	Output is correct
3	Correct	68 ms	156836 KB	Output is correct
4	Correct	76 ms	156868 KB	Output is correct
5	Correct	80 ms	156856 KB	Output is correct
6	Correct	77 ms	156804 KB	Output is correct
7	Correct	75 ms	156792 KB	Output is correct
8	Correct	151 ms	156944 KB	Output is correct
9	Correct	246 ms	157140 KB	Output is correct
10	Correct	248 ms	157124 KB	Output is correct
11	Correct	253 ms	157216 KB	Output is correct
12	Correct	260 ms	157224 KB	Output is correct
13	Correct	229 ms	157436 KB	Output is correct
14	Correct	231 ms	157272 KB	Output is correct
15	Correct	301 ms	157316 KB	Output is correct
16	Correct	333 ms	157296 KB	Output is correct
17	Correct	237 ms	157304 KB	Output is correct
18	Correct	229 ms	157312 KB	Output is correct
19	Correct	316 ms	157376 KB	Output is correct
20	Correct	303 ms	157252 KB	Output is correct