Submission #480686

#	Time	Username	Problem	Language	Result	Execution time	Memory
480686		MilosMilutinovic	Growing Trees (BOI11_grow)	C++14	0 / 100	321 ms	2628 KiB

grow

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=100*1007;

int n, q;

int tab[nax];

ll fen[nax];

void dodaj(int a, int b, int w)
{
    for (int i=b; i; i-=(i&(-i)))
		fen[i]+=w;
    for (int i=a-1; i; i-=(i&(-i)))
		fen[i]-=w;
}

int get(int v)
{
    int ret=0;
    for (int i=v; i<nax; i+=(i&(-i)))
        ret+=fen[i];
    return ret;
}

int getl(int h)
{
    int bot=1, top=n, ans=n+1;
    while (bot<=top)
	{
        int mid=bot+top>>1;
        if (get(mid)>=h)
		{
			ans=mid;
			top=mid-1;
        }
        else
		{
            bot=mid+1;
		}
	}
	return ans;
}

int main()
{
//    scanf("%d %d", &n, &q);
	cin >> n >> q;
    for (int i=1; i<=n; i++)
	{
		cin >> tab[i];
        //scanf("%d", &tab[i]);
	}
	sort(tab+1, tab+n+1);
    for (int i=1; i<=n; i++)
	{
        dodaj(i, i, tab[i]);
	}
    while (q--)
	{
        char typ;
        cin >> typ;
//        scanf("\n%c",&typ);
        if (typ=='F')
		{
			int c, h;
			cin >> c >> h;
//			scanf("%d %d", &c, &h);
            int L = getl(h), R = min(n, L+c-1);
            if (get(L)!=get(R))
			{
                int gde=getl(get(R))-1;
                dodaj(L, gde, 1);
                c-=(gde-L+1);
                int pos=getl(get(R)+1)-1;
                dodaj(pos, pos-c+1, 1);
			}
			else
			{
                int gde=getl(get(tab[R]+1))-1;
                dodaj(max(L, gde-c+1), gde, 1);
			}
		}
		else
		{
            int L,R;
            cin >> L >> R;
//            scanf("%d %d", &L, &R);
//            printf("%d\n", getl(R+1)-getl(L));
			cout << getl(R+1)-getl(L) << "\n";
		}
	}
    return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int getl(int)':
grow.cpp:39:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid=bot+top>>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