제출 #1039591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039591		trucmai	Growing Trees (BOI11_grow)	C++17	0 / 100	1088 ms	10068 KiB

grow

    #include <bits/stdc++.h>
    #ifdef LOCAL
        #include "/home/trcmai/code/tools.h"
        #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
    #else
        #define debug(x...)
    #endif
    using namespace std;
    #define all(a) a.begin(), a.end()
    #define ll long long
    #define endl '\n'
    const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
    const ll INF = 1e18;
    int n,q; 
    namespace segtree{
        int n;
        vector<ll>tr,lz;
        void init(int sz){
            n = sz;
            tr.resize(4*n + 5,0);
            lz.resize(4*n + 5,0);
        }
        void push(int i,int l,int r){
            if(lz[i] == 0) return;
            tr[i] += lz[i];
            if(l != r){
                lz[2*i] += lz[i];
                lz[2*i + 1] += lz[i];
            }
            lz[i] = 0;
        }   
        void update(int i,int l,int r,int ql,int qr,int val){
            push(i,l,r);
            if(l > qr || r < ql) return;
            if(ql <= l && r <= qr){
                lz[i] += val;
                push(i,l,r);
                return;
            }
            int m = (r+l) >> 1; 
            update(2*i,l,m,ql,qr,val);
            update(2*i+1,m+1,r,ql,qr,val);
            tr[i] = max(tr[2*i],tr[2*i + 1]);
        }
        ll get(int i,int l,int r,int ql,int qr){
            push(i,l,r);
            if(l > qr || r < ql) return 0;
            if(ql <= l && r <= qr) return tr[i];
            int m = (r+l) >> 1; 
            return max(get(2*i,l,m,ql,qr),get(2*i+1,m+1,r,ql,qr));
        }
        int walk(int i,int l,int r,ll val){
            push(i,l,r);
            if(tr[i] < val) return n + 1; 
            if(l == r) return l;
            int m = (r+l) >> 1;
            if(tr[2*i] >= val) return walk(2*i,l,m,val);
            else return walk(2*i + 1,m + 1,r,val);
        }
        int walk(ll val){
            return walk(1,1,n,val);
        }
        void update(int l,int r,ll val){ 
            update(1,1,n,l,r,val);
        }
        ll fval(int pos){
            return get(1,1,n,pos,pos);
        }
    }
    signed main() {
        cin.tie(0)->sync_with_stdio(0);
       
        auto solver=[&](){
            cin>>n>>q;
            segtree::init(n);
            vector<int>a(n + 1);
            for(int i = 1;i <= n;++i) cin>>a[i];
            sort(a.begin() + 1,a.end());
            for(int i = 1;i <= n;++i){
                segtree::update(i,i,a[i]);
            } 
            while(q--){
                char t;  cin>>t;
                if(t == 'F'){
                    ll tot,val; cin>>tot>>val;
                    cerr<<"QUERY UPDATE: "<<tot<<" "<<val<<endl;
                    int l = segtree::walk(val);
                    if(l > n) continue; 
                    tot = min(tot,(ll)n - l + 1);
                    ll last_val = segtree::fval(l + tot - 1);
                    //update first range
                    int r = segtree::walk(last_val) - 1;
                    segtree::update(l,r,1);
                    // update second range
                    int r2 = segtree::walk(last_val + 1) - 1; 
                    int l2 = r2 - (tot - (r - l + 1)) + 1;
                    segtree::update(l2,r2,1);
                    
                    cerr<<"RANGE UPDATE: "<<l<<" "<<l + tot - 1<<endl;
                    for(int i = 1;i <= n;++i)
                       cerr<<segtree::fval(i)<<" \n"[i == n];
                    cerr<<endl;
                }else{
                    ll u,v; cin>>u>>v;
                    cerr<<"QUERY ANS: "<<u<<" "<<v<<endl;
                    int l = segtree::walk(u);
                    int r = segtree::walk(v + 1);
                    cerr<<"RANGE ANS: "<<l<<" "<<r<<endl;
                    cout<< r - l << endl;
                }
            }
        };
        int t = 1; // cin>>t;
        while (t--) solver();
    }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10