oj.uz

Submission #56111

# Submission time Handle Problem Language Result Execution time Memory
56111 2018-07-10T04:24:08 Z 김현수(#2106) Growing Trees (BOI11_grow) C++11
100 / 100
 189 ms 40576 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e9;
ll n, q, h[100005];

struct segtree {
    ll val[444444], lim;
    void init (ll N) {
        for(lim=1;lim<=N;lim<<=1);
    }
    void update (ll P, ll V) {
        P += lim;
        while(P) {
            val[P] += V;
            P>>=1;
        }
    }
    ll query (ll S, ll E) {
        ll ret = 0;
        S += lim; E += lim;
        while(S<=E) {
            if(S%2==1) ret += val[S++];
            if(E%2==0) ret += val[E--];
            S>>=1; E>>=1;
        }
        return ret;
    }
    ll firstover (ll K) {
        ll cur = 0, P = 1;
        while(P<lim) {
            if(val[2*P]+cur<K) {
                cur += val[2*P];
                P = 2*P+1;
            }
            else P = 2*P;
        }
        return P-lim;
    }
}seg;

int main()
{
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&h[i]);
    sort(h+1, h+1+n);
    seg.init(n);
    for(ll i=n;i--;) seg.update(i, h[i+1]-h[i]);
    seg.update(n, inf);
    while(q--) {
        char typ[2];
        ll A, B;
        scanf("%s%lld%lld",&typ,&B,&A);
        if(typ[0]=='F') {
            ll as = seg.firstover(A);
            ll tmp = seg.query(0, min(n,as+B));
            ll ae = seg.firstover(tmp);
            ll be = seg.firstover(tmp+1);
            ll bs = max(ae, be-(B-(ae-as)));
            seg.update(as, 1); seg.update(ae, -1);
            seg.update(bs, 1); seg.update(be, -1);
        }
        else {
            printf("%lld\n",seg.firstover(A+1)-seg.firstover(B));
        }
    }
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:53:38: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[2]' [-Wformat=]
         scanf("%s%lld%lld",&typ,&B,&A);
                            ~~~~      ^
grow.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~
grow.cpp:45:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++) scanf("%lld",&h[i]);
                          ~~~~~^~~~~~~~~~~~~~
grow.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%lld%lld",&typ,&B,&A);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4472 KB Output is correct
2 Correct 189 ms 6140 KB Output is correct
3 Correct 95 ms 7696 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7696 KB Output is correct
2 Correct 4 ms 7696 KB Output is correct
3 Correct 5 ms 7696 KB Output is correct
4 Correct 3 ms 7696 KB Output is correct
5 Correct 66 ms 7696 KB Output is correct
6 Correct 75 ms 7696 KB Output is correct
7 Correct 7 ms 7696 KB Output is correct
8 Correct 36 ms 8200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9268 KB Output is correct
2 Correct 61 ms 10192 KB Output is correct
3 Correct 5 ms 10192 KB Output is correct
4 Correct 37 ms 10892 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 12112 KB Output is correct
2 Correct 83 ms 12944 KB Output is correct
3 Correct 8 ms 12944 KB Output is correct
4 Correct 62 ms 14196 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16432 KB Output is correct
2 Correct 103 ms 18732 KB Output is correct
3 Correct 23 ms 18732 KB Output is correct
4 Correct 66 ms 20272 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21548 KB Output is correct
2 Correct 96 ms 22824 KB Output is correct
3 Correct 81 ms 24212 KB Output is correct
4 Correct 19 ms 24212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 25776 KB Output is correct
2 Correct 77 ms 27060 KB Output is correct
3 Correct 80 ms 28468 KB Output is correct
4 Correct 29 ms 28468 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 30616 KB Output is correct
2 Correct 106 ms 31824 KB Output is correct
3 Correct 43 ms 32404 KB Output is correct
4 Correct 70 ms 32884 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 35000 KB Output is correct
2 Correct 94 ms 36400 KB Output is correct
3 Correct 162 ms 37748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 40576 KB Output is correct