oj.uz

Submission #250244

# Submission time Handle Problem Language Result Execution time Memory
250244 2020-07-17T10:04:42 Z generic_placeholder_name Growing Trees (BOI11_grow) C++17
100 / 100
 169 ms 6204 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5112 KB Output is correct
2 Correct 125 ms 5496 KB Output is correct
3 Correct 99 ms 5496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 46 ms 1656 KB Output is correct
6 Correct 54 ms 1912 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 20 ms 1408 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1912 KB Output is correct
2 Correct 54 ms 2168 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 34 ms 1536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2168 KB Output is correct
2 Correct 60 ms 2000 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 56 ms 2040 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3328 KB Output is correct
2 Correct 109 ms 5240 KB Output is correct
3 Correct 17 ms 1664 KB Output is correct
4 Correct 81 ms 5112 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4856 KB Output is correct
2 Correct 107 ms 5240 KB Output is correct
3 Correct 100 ms 5368 KB Output is correct
4 Correct 16 ms 1664 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4980 KB Output is correct
2 Correct 73 ms 5112 KB Output is correct
3 Correct 96 ms 5496 KB Output is correct
4 Correct 16 ms 1664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5700 KB Output is correct
2 Correct 112 ms 5112 KB Output is correct
3 Correct 35 ms 4600 KB Output is correct
4 Correct 55 ms 5004 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5496 KB Output is correct
2 Correct 113 ms 5496 KB Output is correct
3 Correct 169 ms 5752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6204 KB Output is correct