제출 #1088446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088446		thdh__	Growing Trees (BOI11_grow)	C++17	0 / 100	153 ms	7508 KiB

grow

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 1e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

int n,m, st[4*N], lazy[4*N];
vector<int> h;

void push(int id)
{
	st[id*2] += lazy[id], st[id*2+1] += lazy[id];
	lazy[id*2] += lazy[id], lazy[id*2+1] += lazy[id];
	lazy[id] = 0;
}

void update(int id,int l,int r,int u,int v,int val)
{
	if (l>v || r<u) return;
	if (u<=l && r<=v) {st[id] += val, lazy[id] += val; return;}
	push(id);
	int mid = l+r>>1;
	update(id*2,l,mid,u,v,val); update(id*2+1,mid+1,r,u,v,val);
	st[id] = max(st[id*2],st[id*2+1]);
}

int lb(int u)
{
	int l = 0, r = n-1, id = 1;
	if (st[1] < u) return n;
	while (l<r) 
	{
		push(id);
		int mid = l+r>>1;
		if (st[id*2] >= u) id *=2, r = mid;
		else id = id*2+1, l = mid+1;
	}
	return l;
}

int get(int i)
{
	int l = 0, r = n-1, id = 1;
	while (l<r) 
	{
		push(id);
		int mid = l+r>>1;
		if (i>mid) l = mid+1, id = id*2+1;
		else r = mid, id = id*2;
	}
	return st[id];
}

void solve()
{
	cin>>n>>m;
	h.resize(n);
	for (int i=0;i<n;i++) cin>>h[i];
	sort(h.begin(),h.end());
	for (int i=0;i<n;i++) update(1,0,n-1,i,i,h[i]);
	while (m--)
	{
		char type; cin>>type;
		if (type=='F') 
		{
			int c, x; cin>>c>>x;
			int pos = lb(x);
			//cout<<pos<<endl;
			if (x != n) 
			{
				int num = min(c,n-pos+1);
				int nxtval = get(pos+num-1);
				int tmp = lb(nxtval)-1;
				//cout<<pos<<" "<<lb(nxtval)-1<<endl;
				update(1,0,n-1,pos,tmp,1);
				int nxt = lb(nxtval+1)-1;
				//cout<<nxt<<endl;
				update(1,0,n-1,nxt-(c-(tmp-pos+1))+1,nxt,1);
			}
		} else 
		{
			int l,r; cin>>l>>r;
			cout<<lb(r+1)-lb(l)<<endl;
		}
		// for (int i=0;i<n;i++) cout<<get(i)<<" ";
		// cout<<endl;
	}
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

grow.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
grow.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid = l+r>>1;
      |            ~^~
grow.cpp: In function 'long long int lb(long long int)':
grow.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l+r>>1;
      |             ~^~
grow.cpp: In function 'long long int get(long long int)':
grow.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l+r>>1;
      |             ~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10