oj.uz

답안 #1088446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088446 2024-09-14T12:07:21 Z thdh__ Growing Trees (BOI11_grow) C++17
0 / 100
 153 ms 7508 KB 
#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";
	}
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Incorrect 5 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 1828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 6172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 6136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 130 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 153 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -