oj.uz

Submission #994401

# Submission time Handle Problem Language Result Execution time Memory
994401 2024-06-07T14:27:33 Z Khanhcsp2 Growing Trees (BOI11_grow) C++14
100 / 100
 461 ms 5240 KB 
#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
int n, q, a[N], nod[4*N];
void update(int id, int l, int r, int a, int b, int v)
{
    if(l>b || r<a) return;
    if(a<=l && r<=b)
    {
        nod[id]+=v;
        return;
    }
    int mid=(l+r)/2;
    update(id*2, l, mid, a, b, v);
    update(id*2+1, mid+1, r, a, b, v);
//    nod[id]=(nod[id*2]+ nod[id*2+1]);
}
int get(int id, int l, int r, int a, int b)
{
    if(l>b || r<a) return 0;
    if(a<=l && r<=b) return nod[id];
    int mid=(l+r)/2;
    return nod[id]+get(id*2, l, mid, a, b)+get(id*2+1, mid+1, r, a, b);
}
int f1(int x)
{
    int l=1, r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(get(1, 1, n, mid, mid)>=x)
        {
            r=mid-1;
        }
        else l=mid+1;
    }
    return l;
}
int f2(int x)
{
    int l=1, r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(get(1, 1, n, mid, mid)>x)
        {
            r=mid-1;
        }
        else l=mid+1;
    }
    return l;
}
void sol()
{
    cin >> n >> q;
    for(int i=1, x; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) update(1, 1, n, i, i, a[i]);
    while(q--)
    {
        char tt;
        cin >> tt;
        if(tt=='F')
        {
            int u, v;
            cin >> u >> v;
            int pos=f1(v);
            if(pos<=n)
            {
                int p=min(pos+u-1,n);
                int l=f1(get(1,1,n,p,p));
                int r=f2(get(1,1,n,p,p));
                int need=p-l+1;
                update(1,1,n,pos,l-1,1);
                update(1,1,n,r-need,r-1,1);
            }
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << f2(r)-f1(l) << el;
        }
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Compilation message

grow.cpp: In function 'void sol()':
grow.cpp:66:18: warning: unused variable 'x' [-Wunused-variable]
   66 |     for(int i=1, x; i<=n; i++) cin >> a[i];
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 3408 KB Output is correct
2 Correct 369 ms 4944 KB Output is correct
3 Correct 328 ms 4944 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 129 ms 1656 KB Output is correct
6 Correct 141 ms 1816 KB Output is correct
7 Correct 11 ms 600 KB Output is correct
8 Correct 101 ms 1396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 848 KB Output is correct
2 Correct 160 ms 1876 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 119 ms 1344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 852 KB Output is correct
2 Correct 168 ms 1952 KB Output is correct
3 Correct 19 ms 600 KB Output is correct
4 Correct 162 ms 1872 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 3164 KB Output is correct
2 Correct 348 ms 4632 KB Output is correct
3 Correct 47 ms 3164 KB Output is correct
4 Correct 244 ms 4436 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 3164 KB Output is correct
2 Correct 346 ms 4692 KB Output is correct
3 Correct 309 ms 4688 KB Output is correct
4 Correct 46 ms 3164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 3412 KB Output is correct
2 Correct 224 ms 4688 KB Output is correct
3 Correct 302 ms 4940 KB Output is correct
4 Correct 46 ms 3164 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 3364 KB Output is correct
2 Correct 348 ms 4436 KB Output is correct
3 Correct 61 ms 4164 KB Output is correct
4 Correct 258 ms 4568 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 3612 KB Output is correct
2 Correct 349 ms 4880 KB Output is correct
3 Correct 461 ms 5240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 3920 KB Output is correct