Submission #526263

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526263	2022-02-14T06:09:59 Z	tmn2005	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	386 ms	236124 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 = 15e6+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	117 ms	235052 KB	Output is correct
2	Correct	108 ms	235084 KB	Output is correct
3	Correct	105 ms	235052 KB	Output is correct
4	Correct	116 ms	235144 KB	Output is correct
5	Correct	118 ms	235044 KB	Output is correct
6	Correct	114 ms	235144 KB	Output is correct
7	Correct	114 ms	235076 KB	Output is correct
8	Correct	239 ms	235236 KB	Output is correct
9	Correct	288 ms	235844 KB	Output is correct
10	Correct	307 ms	235960 KB	Output is correct
11	Correct	315 ms	235932 KB	Output is correct
12	Correct	320 ms	236040 KB	Output is correct
13	Correct	285 ms	236088 KB	Output is correct
14	Correct	324 ms	236108 KB	Output is correct
15	Correct	373 ms	236036 KB	Output is correct
16	Correct	347 ms	236036 KB	Output is correct
17	Correct	295 ms	236068 KB	Output is correct
18	Correct	286 ms	236124 KB	Output is correct
19	Correct	386 ms	236096 KB	Output is correct
20	Correct	351 ms	236016 KB	Output is correct