Submission #250244

#	Time	Username	Problem	Language	Result	Execution time	Memory
250244		generic_placeholder_name	Growing Trees (BOI11_grow)	C++17	100 / 100	169 ms	6204 KiB

grow

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
 
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename _def> using ordered_set=tree<_def, null_type, less<_def>, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
 
constexpr int N=100001;
int mx[4*N+4], mn[4*N+4], lz[4*N+4];
int a[N];
int n;
 
void build(int a[], int v=1, int l=0, int r=n-1) {
    if(l==r) mx[v]=mn[v]=a[l];
    else {
        int m=(l+r)/2;
        build(a, v*2, l, m);
        build(a, v*2+1, m+1, r);
        mx[v]=max(mx[v*2], mx[v*2+1]);
        mn[v]=min(mn[v*2], mn[v*2+1]);
    }
}
 
void push(int v) {
    mx[v*2]+=lz[v];
    mn[v*2]+=lz[v];
    lz[v*2]+=lz[v];
    mx[v*2+1]+=lz[v];
    mn[v*2+1]+=lz[v];
    lz[v*2+1]+=lz[v];
    lz[v]=0;
}
 
void upd(int ql, int qr, int v=1, int l=0, int r=n-1) {
    if(ql>r||qr<l) return;
    if(ql<=l&&qr>=r) {
        mn[v]++; mx[v]++;
        lz[v]++;
    }
    else {
        push(v);
        int m=(l+r)/2;
        upd(ql, qr, v*2, l, m);
        upd(ql, qr, v*2+1, m+1, r);
        mx[v]=max(mx[v*2], mx[v*2+1]);
        mn[v]=min(mn[v*2], mn[v*2+1]);
    }
}
 
int getl(int val, int v=1, int l=0, int r=n-1) {
    if(mx[v]<=val) return r-l+1;
    if(mn[v]>val) return 0;
    push(v);
    int m=(l+r)/2;
    return getl(val, v*2, l, m)+getl(val, v*2+1, m+1, r);
}
 
int get(int pos, int v=1, int l=0, int r=n-1) {
    if(l==r) return mx[v];
    else {
        push(v);
        int m=(l+r)/2;
        if(pos<=m) return get(pos, v*2, l, m);
        else return get(pos, v*2+1, m+1, r);
    }
}
 
int32_t main() {
	fastio;
	int m; cin>>n>>m;
	rep(i, n) cin>>a[i];
	sort(a, a+n);
	build(a);
	//rep(i, n) cout<<get(i)<<' '; cout<<endl;
	rep(i, m) {
        char t; cin>>t;
        if(t=='C') {
            int l, r; cin>>l>>r; cout<<getl(r)-getl(l-1)<<endl;
        }
        else {
            int c, h; cin>>c>>h;
            int lpos=getl(h-1);
            if(lpos==n) continue; //if larger continue
            int rpos=min(lpos+c, n)-1; c=rpos-lpos+1;
            int lst=get(rpos);
            int pre=getl(lst-1)-1;
            int nxt=getl(lst)-1;
            int pre_nxt=nxt-(c-(pre-lpos+1))+1;
            //cout<<lpos<<' '<<pre<<' '<<pre_nxt<<' '<<nxt<<endl;
            upd(lpos, pre);
            upd(pre_nxt, nxt);
        }
        //rep(i, n) cout<<get(i)<<' '; cout<<endl;
	}
}

Compilation message (stderr)

grow.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops, no-stack-protector")

• 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