oj.uz

답안 #842870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842870 2023-09-03T12:32:35 Z vjudge1 Growing Trees (BOI11_grow) C++17
0 / 100
 1000 ms 6692 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 lazy[4*maxn];

    void build(int id, int l, int r)
    {
        if(l == r){
            tree[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]);
    }

    void down(int id, int l, int r)
    {
        if(lazy[id] == 0)
            return;
        tree[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]);
    }

    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 Find_min(int id, int l, int r, int val)
    {
        down(id, l, r);
        if(l == r){
            if(tree[id] >= val){
                return l;
            }
            return -1;
        }
        int mid = l + r >> 1;
        int id_1 = Find_min(id*2, l, mid, val);
        if(id_1 != -1){
            return id_1;
        }
        else{
            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){
            if(tree[id] <= val){
                return l;
            }
            return -1;
        }
        int mid = l + r >> 1;
        int id_1 = Find_max(id*2+1, mid+1, r, val);
        if(id_1 != -1){
            return id_1;
        }
        else{
            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:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         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:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         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:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'long long int Seg::Find_min(long long int, long long int, long long int, long long int)':
grow.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'long long int Seg::Find_max(long long int, long long int, long long int, long long int)':
grow.cpp:103:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1036 ms 6496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2396 KB Output is correct
2 Correct 20 ms 2588 KB Output is correct
3 Correct 12 ms 2396 KB Output is correct
4 Correct 8 ms 2396 KB Output is correct
5 Execution timed out 1094 ms 3280 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1054 ms 2976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 863 ms 3304 KB Output is correct
2 Execution timed out 1080 ms 3156 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 6440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1057 ms 6312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1026 ms 6480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1062 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1028 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1045 ms 6692 KB Time limit exceeded
2 Halted 0 ms 0 KB -