Submission #870950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870950	2023-11-09T15:06:48 Z	Hyojin	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	211 ms	190288 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=1e5+5;
struct segtree{
	int idL,idR,sum,lazy;
	segtree():idL(0),idR(0),sum(0),lazy(0){}
} st[N*4*30];
int cur;
void update(int id,int x,int l,int r)
{
	st[id].sum=r-l+1;
	st[id].lazy=x;
}
void down(int id,int l,int mid,int r)
{
	if (st[id].idL==0) st[id].idL=++cur;
	if (st[id].idR==0) st[id].idR=++cur;
	if (st[id].lazy!=0)
	{
		update(st[id].idL,st[id].lazy,l,mid);
		update(st[id].idR,st[id].lazy,mid+1,r);
		st[id].lazy=0;
	}
}
void update(int id,int l,int r,int u,int v)
{
	if (v<l||r<u) return;
	if (u<=l&&r<=v)
	{
		st[id].lazy++;
		st[id].sum=(r-l+1);
		return;
	}
	int mid=l+r>>1;
	down(id,l,mid,r);
	update(st[id].idL,l,mid,u,v);
	update(st[id].idR,mid+1,r,u,v);
	st[id].sum=st[st[id].idL].sum+st[st[id].idR].sum;
}
int get(int id,int l,int r,int u,int v)
{
	if (u<=l&&r<=v) return st[id].sum;
	int mid=l+r>>1;
	down(id,l,mid,r);
	if (v<=mid) return get(st[id].idL,l,mid,u,v);
	if (mid+1<=u) return get(st[id].idR,mid+1,r,u,v);
	return get(st[id].idL,l,mid,u,v)+get(st[id].idR,mid+1,r,u,v);
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef Shiho
    	freopen("izumi_shiho_supremacy.in","r", stdin);
    	freopen("izumi_shiho_supremacy.out","w", stdout);
	#endif
	cur=1;
	int q;
	cin>>q;
	int c=0;
	while (q--)
	{	
		int type,u,v;
		cin>>type>>u>>v;
		if (type==1) 
		{
			int x=get(1,1,1e9,u+c,v+c);
			c=x;
			cout<<x<<"\n";
		}
		else 
		{
			update(1,1,1e9,u+c,v+c);
		}
	}
	return 0;	
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  int mid=l+r>>1;
      |          ~^~
apple.cpp: In function 'int get(int, int, int, int, int)':
apple.cpp:56:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid=l+r>>1;
      |          ~^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	188100 KB	Output is correct
2	Correct	57 ms	188240 KB	Output is correct
3	Correct	58 ms	188356 KB	Output is correct
4	Correct	62 ms	188240 KB	Output is correct
5	Correct	64 ms	188500 KB	Output is correct
6	Correct	62 ms	188356 KB	Output is correct
7	Correct	66 ms	188496 KB	Output is correct
8	Correct	98 ms	189084 KB	Output is correct
9	Correct	145 ms	189708 KB	Output is correct
10	Correct	196 ms	189520 KB	Output is correct
11	Correct	170 ms	189632 KB	Output is correct
12	Correct	151 ms	189604 KB	Output is correct
13	Correct	158 ms	190000 KB	Output is correct
14	Correct	155 ms	190288 KB	Output is correct
15	Correct	175 ms	189856 KB	Output is correct
16	Correct	211 ms	190028 KB	Output is correct
17	Correct	152 ms	189856 KB	Output is correct
18	Correct	148 ms	190036 KB	Output is correct
19	Correct	174 ms	190032 KB	Output is correct
20	Correct	172 ms	190056 KB	Output is correct