oj.uz

Submission #480686

# Submission time Handle Problem Language Result Execution time Memory
480686 2021-10-17T18:12:43 Z MilosMilutinovic Growing Trees (BOI11_grow) C++14
0 / 100
 321 ms 2628 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 2628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 1952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 2208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 2200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 2608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 2432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 1912 KB Output isn't correct