oj.uz

답안 #870950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870950 2023-11-09T15:06:48 Z Hyojin 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 211 ms 190288 KB 
#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

# 결과 실행 시간 메모리 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