oj.uz

Submission #480685

# Submission time Handle Problem Language Result Execution time Memory
480685 2021-10-17T18:10:22 Z MilosMilutinovic Growing Trees (BOI11_grow) C++14
0 / 100
 134 ms 4152 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);
    for (int i=1; i<=n; 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;
        scanf("\n%c",&typ);
        if (typ=='F')
		{
			int 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;
            scanf("%d %d", &L, &R);
            printf("%d\n", getl(R+1)-getl(L));
		}
	}
    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;
      |                 ~~~^~~~
grow.cpp: In function 'int main()':
grow.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d", &tab[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
grow.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("\n%c",&typ);
      |         ~~~~~^~~~~~~~~~~~~
grow.cpp:72:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |    scanf("%d %d", &c, &h);
      |    ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |             scanf("%d %d", &L, &R);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 3148 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 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 1348 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 2 ms 716 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 17 ms 2508 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 17 ms 2712 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 14 ms 2636 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 124 ms 4152 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 24 ms 3148 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 134 ms 3652 KB Output isn't correct