oj.uz

답안 #1039601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039601 2024-07-31T05:15:04 Z trucmai Growing Trees (BOI11_grow) C++17
10 / 100
 95 ms 4036 KB 
#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;
ll a[N];
namespace fenwick{
    ll tr[N];
    void add(int i,ll val){
        for(;i < N;i += i&(-i)) tr[i] += val;
    }   
    void upd(int l,int r,ll val){
        if(l > r) return;
        r = min(r,n);
        add(l,val);
        add(r+1,-val);
    }
    ll get(int i){
        ll res = 0;
        for(;i > 0;i -= i&(-i)) res += tr[i];
        return res;
    }
    int walk(ll val){
        int l = 1,r = n + 1;
        while(l < r){
            int m = (r+l) >> 1; 
            if(get(m) >= val) r = m;
            else l = m + 1;
        }
        return l;
    }
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    auto solver=[&](){
        cin>>n>>q;
        for(int i = 1;i <= n;++i) cin>>a[i];
        sort(a + 1,a + n + 1);
        for(int i = 1;i <= n;++i)
            fenwick::add(i,a[i] - a[i - 1]);
        while(q--){
            char t; cin>>t;
            if(t == 'F'){
                int tot; ll val; cin>>tot>>val;
                int l = fenwick::walk(val);
                int r = min(n,l + tot - 1);
                if(l > n) return; 
                tot = r - l + 1;
                ll last_val = fenwick::get(r);
                int s = fenwick::walk(last_val);
                int t = fenwick::walk(last_val + 1) - 1;
                if(l >= s){
                    fenwick::upd(t - tot + 1,t,1);
                }else{
                    fenwick::upd(l,s - 1,1);
                    tot -= s - l;
                    fenwick::upd(t - tot + 1,t,1);
                }
            }else{
                ll low,high; cin>>low>>high;
                cout<<fenwick::walk(high + 1) - fenwick::walk(low) << endl;
            }
        }
    };
    int t = 1; // cin>>t;
    while (t--) solver();
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 2140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 32 ms 1620 KB Output is correct
6 Incorrect 2 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 3168 KB Output is correct
2 Incorrect 12 ms 2136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 4036 KB Output is correct