Submission #526264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526264	2022-02-14T06:12:33 Z	tmn2005	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	308 ms	157424 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;
		
		push(t[v].fr, m - l + 1);
		push(t[v].sc, r - m);
		
 		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:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	156820 KB	Output is correct
2	Correct	70 ms	156812 KB	Output is correct
3	Correct	68 ms	156748 KB	Output is correct
4	Correct	76 ms	156868 KB	Output is correct
5	Correct	80 ms	156768 KB	Output is correct
6	Correct	79 ms	156840 KB	Output is correct
7	Correct	79 ms	156880 KB	Output is correct
8	Correct	151 ms	156996 KB	Output is correct
9	Correct	255 ms	157312 KB	Output is correct
10	Correct	251 ms	157180 KB	Output is correct
11	Correct	255 ms	157232 KB	Output is correct
12	Correct	264 ms	157244 KB	Output is correct
13	Correct	232 ms	157320 KB	Output is correct
14	Correct	235 ms	157328 KB	Output is correct
15	Correct	305 ms	157324 KB	Output is correct
16	Correct	305 ms	157252 KB	Output is correct
17	Correct	240 ms	157396 KB	Output is correct
18	Correct	252 ms	157252 KB	Output is correct
19	Correct	305 ms	157252 KB	Output is correct
20	Correct	308 ms	157424 KB	Output is correct