제출 #842892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842892		vjudge1	Growing Trees (BOI11_grow)	C++17	100 / 100	412 ms	9828 KiB

grow

#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 ///

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10