oj.uz

Submission #91693

# Submission time Handle Problem Language Result Execution time Memory
91693 2018-12-29T08:41:53 Z Tieuphong Growing Trees (BOI11_grow) C++11
50 / 100
 1000 ms 5664 KB 
/***************************************************************************/
/**********************  LANG TU HAO HOA  **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 1000000007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 100005
#define task "grow"
#define remain(x) ((x > MOD) ? (x - MOD) : x)

template<class T> void read(T &x){char c;bool nega = 0;while(!isdigit(c = getchar()) && c != '-');if(c == '-') nega = 1,c = getchar();x = c - 48;while(isdigit(c = getchar())) x = x * 10 + c - 48;}
template<class T> void writep(T x){if(x > 9) writep(x/10);putchar(x % 10 + 48);}
template<class T> void write(T x){if(x < 0) putchar('-'),x = -x;writep(x);putchar(' ');}
template<class T> void writeln(T x){write(x);putchar('\n');}

using namespace std;

int n, m, h[N];

vector <int> luu, v;

void Sub1()
{
    FOR(i, 1, m)
    {
        char c;
        int x, y;
        c = getchar();
        read(x), read(y);//cin >> c >> x >> y;
        if (c == 'F')
        {
            int pos = lower_bound(h+1, h+n+1, y) - h;
            x = min(x, n-pos+1);
            int val = h[pos+x-1];
            int l = lower_bound(h+pos, h+n+1, val) - h;
            int r = upper_bound(h+pos, h+n+1, val) - h - 1;
            FOR(i, pos, l-1) h[i]++;
            x -= (l - pos);
            FORD(i, r, r-x+1) h[i]++;
        }
            else
            {
                int res = upper_bound(h+1, h+n+1, y) - lower_bound(h+1, h+n+1, x);
                writeln(res);
            }
    }
}

struct IT
{
    pii t[N << 2];
    int lazy[N<<2];

    void Build (int l, int r, int id)
    {
        if (l == r)
        {
            t[id] = MP(h[l], h[l]);
            return;
        }
        int mid = (l + r) >> 1;
        Build(l, mid, id*2);
        Build(mid+1, r, id*2+1);
        t[id].F = max(t[id*2].F, t[id*2+1].F);
        t[id].S = min(t[id*2].S, t[id*2+1].S);
    }

    void Push(int l, int r, int id)
    {
        if (!lazy[id]) return;
        t[id].F += lazy[id];
        t[id].S += lazy[id];
        if (l == r) {lazy[id] = 0; return;}
        lazy[id*2] += lazy[id];
        lazy[id*2+1] += lazy[id];
        lazy[id] = 0;
    }

    void Upd(int l, int r, int id, int u, int v)
    {
        if (l > v || r < u) return;
        if (l >= u && r <= v)
        {
            lazy[id]++;
            Push(l, r, id);
            return;
        }
        Push(l, r, id);
        int mid = (l + r) >> 1;
        Upd(l, mid, id*2, u, v);
        Upd(mid+1, r, id*2+1, u, v);
        t[id].F = max(t[id*2].F, t[id*2+1].F);
        t[id].S = min(t[id*2].S, t[id*2+1].S);
    }

    pii Get(int l, int r, int id, int u, int v)
    {
        if (l > v || r < u) return MP(-maxc, maxc);
        if (l >= u && r <= v)
        {
            Push(l, r, id);
            return t[id];
        }
        Push(l, r, id);
        int mid = (l + r) >> 1;
        pii m1 = Get(l, mid, id*2, u, v);
        pii m2 = Get(mid+1, r, id*2+1, u, v);
        return MP(max(m1.F, m2.F), min(m1.S, m2.S));
    }

    int Find_max(int l, int r, int id, int val)
    {
        if (l == r)
        {
            Push(l, r, id);
            if (t[id].F <= val) return l;
            return -1;
        }
        Push(l, r, id);
        int mid = (l + r) >> 1;
        int cur = Get(1, n, 1, mid+1, n).S;
        if (cur <= val) return Find_max(mid+1, r, id*2+1, val);
        return Find_max(l, mid, id*2, val);
    }

    int Find_min(int l, int r, int id, int val)
    {
        if (l == r)
        {
            Push(l, r, id);
            if (t[id].S >= val) return l;
            return -1;
        }
        Push(l, r, id);
        int mid = (l + r) >> 1;
        int cur = Get(1, n, 1, 1, mid).F;
        if (cur < val) return Find_min(mid+1, r, id*2+1, val);
        return Find_min(l, mid, id*2, val);
    }

} Tree;

void Full()
{
    Tree.Build(1, n, 1);
    FOR(i, 1, m)
    {
        char c;
        int x, y;
        c = getchar();
        read(x), read(y);//cin >> c >> x >> y;
        if (c == 'F')
        {
            int pos = Tree.Find_min(1, n, 1, y);
            if (pos == -1) continue;
            x = min(x, n-pos+1);
            int val = Tree.Get(1, n, 1, pos, pos+x-1).F;
            int l = Tree.Find_min(1, n, 1, val);
            int r = Tree.Find_max(1, n, 1, val);
            if (pos <= l-1) Tree.Upd(1, n, 1, pos, l-1);
            x -= (l - pos);
            Tree.Upd(1, n, 1, r-x+1, r);
        }
            else
            {
                int l = Tree.Find_min(1, n, 1, x);
                int r = Tree.Find_max(1, n, 1, y);
                int res = r - l + 1;
                if (l == -1 || r == -1) res = 0;
                writeln(res);
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    read(n), read(m);//cin >> n >> m;
    FOR(i, 1, n) read(h[i]);//cin >> h[i];
    sort(h+1, h+n+1);
    Sub1();
    //Full();
    return 0;
}

Compilation message

grow.cpp: In instantiation of 'void read(T&) [with T = int]':
grow.cpp:42:15:   required from here
grow.cpp:24:47: warning: variable 'nega' set but not used [-Wunused-but-set-variable]
 template<class T> void read(T &x){char c;bool nega = 0;while(!isdigit(c = getchar()) && c != '-');if(c == '-') nega = 1,c = getchar();x = c - 48;while(isdigit(c = getchar())) x = x * 10 + c - 48;}
                                               ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 4216 KB Output is correct
2 Correct 298 ms 5624 KB Output is correct
3 Execution timed out 1066 ms 4856 KB Time limit exceeded

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct
3 Correct 5 ms 3576 KB Output is correct
4 Correct 5 ms 3580 KB Output is correct
5 Correct 26 ms 4600 KB Output is correct
6 Correct 31 ms 4916 KB Output is correct
7 Correct 7 ms 3576 KB Output is correct
8 Correct 15 ms 4344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3960 KB Output is correct
2 Correct 38 ms 4984 KB Output is correct
3 Correct 6 ms 3576 KB Output is correct
4 Correct 17 ms 4600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4084 KB Output is correct
2 Correct 33 ms 4984 KB Output is correct
3 Correct 12 ms 3548 KB Output is correct
4 Correct 35 ms 4984 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 4084 KB Output is correct
2 Correct 236 ms 5408 KB Output is correct
3 Correct 12 ms 3960 KB Output is correct
4 Execution timed out 1073 ms 4956 KB Time limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 3948 KB Output is correct
2 Correct 245 ms 5396 KB Output is correct
3 Execution timed out 1085 ms 4744 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4088 KB Output is correct
2 Correct 677 ms 5400 KB Output is correct
3 Execution timed out 1077 ms 4984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 4096 KB Output is correct
2 Correct 114 ms 5208 KB Output is correct
3 Correct 76 ms 4600 KB Output is correct
4 Correct 41 ms 5112 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4280 KB Output is correct
2 Correct 110 ms 5664 KB Output is correct
3 Execution timed out 1076 ms 5464 KB Time limit exceeded

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4472 KB Output is correct