oj.uz

Submission #842892

# Submission time Handle Problem Language Result Execution time Memory
842892 2023-09-03T13:00:02 Z vjudge1 Growing Trees (BOI11_grow) C++17
100 / 100
 412 ms 9828 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 5;

int n, m;
int a[maxn];

struct Seg
{
    int tree[4*maxn];
    int tmin[4*maxn];
    int lazy[4*maxn];

    void build(int id, int l, int r)
    {
        if(l == r){
            tree[id] = tmin[id] = a[l];
            return;
        }

        int mid = l + r >> 1;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);

        tree[id] = max(tree[id*2], tree[id*2+1]);
        tmin[id] = min(tmin[id*2], tmin[id*2+1]);
    }

    void down(int id, int l, int r)
    {
        if(lazy[id] == 0)
            return;
        tree[id] += lazy[id];
        tmin[id] += lazy[id];
        if(l != r){
            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)
    {
        down(id, l, r);
        if(r < u || v < l)
            return;
        if(u <= l && r <= v){
            lazy[id] = val;
            down(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id*2, l, mid, u, v, val);
        update(id*2+1, mid+1, r, u, v, val);

        tree[id] = max(tree[id*2], tree[id*2+1]);
        tmin[id] = min(tmin[id*2], tmin[id*2+1]);
    }

    int get_max(int id, int l, int r, int u, int v)
    {
        down(id, l, r);
        if(r < u || v < l){
            return -1;
        }
        if(u <= l && r <= v){
            return tree[id];
        }
        int mid = l + r >> 1;
        int val_1 = get_max(id*2, l, mid, u, v);
        int val_2 = get_max(id*2+1, mid+1, r, u, v);

        return max(val_1, val_2);
    }

    int get_min(int id, int l, int r, int u, int v)
    {
        down(id, l, r);
        if(r < u || v < l){
            return 1e18;
        }
        if(u <= l && r <= v){
            return tmin[id];
        }
        int mid = l + r >> 1;
        int val_1 = get_min(id*2, l, mid, u, v);
        int val_2 = get_min(id*2+1, mid+1, r, u, v);

        return min(val_1, val_2);
    }

    int Find_min(int id, int l, int r, int val) {
        down(id, l, r);
        if (l == r) {
            if (tmin[id] >= val) return l;
            return -1;
        }

        int mid = (l + r) >> 1;
        int cur = get_max(1, 1, n, 1, mid);
        if (cur >= val)
            return Find_min(id*2, l, mid, val);
        return Find_min(id*2+1, mid + 1, r, val);
     }

     int Find_max(int id, int l, int r, int val) {
        down(id, l, r);
        if (l == r) {
//            cout << l << endl;
            if (tree[id] <= val) return l;
            return -1;
        }

        int mid = (l + r) >> 1;
        int cur = get_min(1, 1, n, mid+1, n);
//        cout << cur << endl;
        if (cur <= val)
            return Find_max(id*2+1, mid + 1, r, val);
        return Find_max(id*2, l, mid, val);
     }
}ST;

signed main()
{
//    freopen("D.inp", "r", stdin);
//    freopen("D.out", "w", stdout);

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i=1 ; i<=n ; ++i){
        cin >> a[i];
    }
    sort(a+1, a+1+n);
    ST.build(1, 1, n);

    for(int i=1 ; i<=m ; ++i){
        char type;
        int l, r;
        cin >> type >> l >> r;
        if (type == 'F') {
            int pos = ST.Find_min(1, 1, n, r);
//            cout << pos << endl;
            if (pos == -1) continue;
            if (pos + l - 1 >= n) {
                ST.update(1, 1, n, pos, n, 1);
                continue;
            }

            int val = ST.get_max(1, 1, n, pos, pos + l - 1);
            int last = ST.Find_min(1, 1, n, val);
            int nxt = ST.Find_max(1, 1, n, val);
            int len = last - pos;

//            cout << val << ' ' << last << ' ' << nxt << ' ' << len << endl;

            ST.update(1, 1, n, pos, last - 1, 1);
            ST.update(1, 1, n, nxt - (l - len) + 1, nxt, 1);
        }
        else {
            int pos = ST.Find_min(1, 1, n, l);
            int last = ST.Find_max(1, 1, n, r);

            if (pos == -1 || last == -1)
                cout << 0 << '\n';
            else
                cout << last - pos + 1 << '\n';
        }
    }
}

/// code by yourlove ///

Compilation message

grow.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
grow.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'void Seg::update(long long int, long long int, long long int, long long int, long long int, long long int)':
grow.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'long long int Seg::get_max(long long int, long long int, long long int, long long int, long long int)':
grow.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'long long int Seg::get_min(long long int, long long int, long long int, long long int, long long int)':
grow.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 9828 KB Output is correct
2 Correct 286 ms 9444 KB Output is correct
3 Correct 101 ms 9392 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 110 ms 2940 KB Output is correct
6 Correct 140 ms 3084 KB Output is correct
7 Correct 9 ms 2648 KB Output is correct
8 Correct 82 ms 2936 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3104 KB Output is correct
2 Correct 138 ms 3104 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 103 ms 3152 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 3152 KB Output is correct
2 Correct 160 ms 3240 KB Output is correct
3 Correct 18 ms 2648 KB Output is correct
4 Correct 137 ms 3156 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6232 KB Output is correct
2 Correct 267 ms 9304 KB Output is correct
3 Correct 36 ms 5208 KB Output is correct
4 Correct 83 ms 9136 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 9360 KB Output is correct
2 Correct 275 ms 9704 KB Output is correct
3 Correct 103 ms 9040 KB Output is correct
4 Correct 36 ms 5468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 9620 KB Output is correct
2 Correct 191 ms 9580 KB Output is correct
3 Correct 102 ms 9296 KB Output is correct
4 Correct 36 ms 5456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 9712 KB Output is correct
2 Correct 314 ms 9304 KB Output is correct
3 Correct 46 ms 9544 KB Output is correct
4 Correct 209 ms 9560 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 9700 KB Output is correct
2 Correct 374 ms 9576 KB Output is correct
3 Correct 412 ms 9528 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9808 KB Output is correct