oj.uz

Submission #905286

# Submission time Handle Problem Language Result Execution time Memory
905286 2024-01-12T22:17:27 Z asdasdqwer Growing Trees (BOI11_grow) C++14
100 / 100
 207 ms 9044 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t

struct Segtree {
    int n;
    int nn;
    vector<int> mn;
    vector<int> mx;
    vector<int> add;

    Segtree(int sz,vector<int> &a) {
        n=1;
        nn=sz;
        while (n<sz)n*=2;
        mn.assign(2*n,1e17);
        mx.assign(2*n,0);
        add.assign(2*n,0);
        build(a,0,0,n);
    }

    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (lx<(int)a.size()) {
                mn[x]=mx[x]=a[lx];
            }
            return;
        }

        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        mx[x]=max(mx[2*x+1],mx[2*x+2]);
        mn[x]=min(mn[2*x+1],mn[2*x+2]);
    }

    void pushdown(int x) {
        if (add[x]==0)return;

        mn[2*x+1]+=add[x];
        mx[2*x+1]+=add[x];
        mn[2*x+2]+=add[x];
        mx[2*x+2]+=add[x];
        add[2*x+1]+=add[x];
        add[2*x+2]+=add[x];
        add[x]=0;
    }

    void inc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;

        if (rx-lx==1) {
            mn[x]++;
            mx[x]++;
            return;
        }

        pushdown(x);

        if (lx >= l && rx <= r) {
            add[x]++;
            mn[x]++;
            mx[x]++;
            return;
        }

        int m=(lx+rx)/2;
        inc(l, r, 2*x+1, lx, m);
        inc(l, r, 2*x+2, m, rx);

        mx[x]=max(mx[2*x+1], mx[2*x+2]);
        mn[x]=min(mn[2*x+1], mn[2*x+2]);
    }

    void inc(int l, int r) {
        inc(l, r, 0, 0, n);
    }

    int first(int v, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (mn[x] < v) return -1;
            return lx;
        }

        pushdown(x);

        int m = (lx+rx)/2;

        if (mx[2*x+1] >= v) {
            return first(v, 2*x+1, lx, m);
        }

        else {
            return first(v, 2*x+2, m, rx);
        }
    }

    int first(int v) {
        return first(v, 0, 0, n);
    }

    int last(int v, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (mn[x] > v) return -1;
            return lx;
        }

        pushdown(x);

        int m=(lx+rx)/2;
        
        if (mn[2*x+2] <= v) return last(v, 2*x+2, m, rx);

        else return last(v, 2*x+1, lx, m);
    }

    int last(int v) {
        return last(v, 0, 0, n);
    }

    int getValue(int i, int x, int lx, int rx) {
        if (rx-lx==1) {
            return mn[x];
        }

        pushdown(x);

        int m=(lx+rx)/2;
        if (i<m)return getValue(i,2*x+1,lx,m);
        else return getValue(i, 2*x+2,m,rx);
    }

    int getValue(int i) {
        return getValue(i, 0, 0, n);
    }

    void query(int start, int numInc) {
        int firstIndex = first(start);

        if (firstIndex == -1 || firstIndex >= nn) return;

        if (firstIndex + numInc - 1 >= nn - 1) {
            inc(firstIndex, nn);
            return;
        }

        int valueOfLast = getValue(firstIndex + numInc - 1);

        int fRange = first(valueOfLast), eRange = last(valueOfLast);
        // cout<<fRange<<" "<<eRange<<"\n";

        int end = firstIndex + numInc - 1;

        if (firstIndex < fRange) {
            inc(firstIndex, fRange);
            numInc -= (fRange - firstIndex);
        }

        inc(eRange - numInc + 1, eRange + 1);
    }

    void all() {
        for (int i=0;i<nn;i++) {
            cout<<getValue(i)<<" ";
        }
        cout<<"\n";
    }
};

signed main() {
    int n,q;cin>>n>>q;
    vector<int> a(n);
    for (int &x:a)cin>>x;
    sort(a.begin(),a.end());

    Segtree sg(n, a);

    for (int i=0;i<q;i++) {
        char d;cin>>d;
        if (d == 'F') {
            int c,h;cin>>c>>h;
            sg.query(h,c);
        }

        else{ 
            int mn,mx;cin>>mn>>mx;
            int f=sg.first(mn);
            if (f==-1 || f >= n){
                cout<<0<<"\n";
                continue;
            }

            int s=sg.last(mx);
            if (s >= n)s=n-1;
            if (s==-1) {
                cout<<0<<"\n";
                continue;
            }

            cout<<s-f+1<<"\n";
        }
    }
}

Compilation message

grow.cpp: In member function 'void Segtree::query(int64_t, int64_t)':
grow.cpp:153:13: warning: unused variable 'end' [-Wunused-variable]
  153 |         int end = firstIndex + numInc - 1;
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 7304 KB Output is correct
2 Correct 186 ms 9044 KB Output is correct
3 Correct 120 ms 8788 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 7 ms 552 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 129 ms 1704 KB Output is correct
6 Correct 165 ms 2068 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 118 ms 1512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1020 KB Output is correct
2 Correct 161 ms 2132 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 136 ms 1692 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 1176 KB Output is correct
2 Correct 179 ms 2164 KB Output is correct
3 Correct 10 ms 860 KB Output is correct
4 Correct 168 ms 2256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4024 KB Output is correct
2 Correct 170 ms 8556 KB Output is correct
3 Correct 43 ms 2484 KB Output is correct
4 Correct 106 ms 8672 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 7252 KB Output is correct
2 Correct 174 ms 7248 KB Output is correct
3 Correct 118 ms 8792 KB Output is correct
4 Correct 43 ms 2396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 7292 KB Output is correct
2 Correct 142 ms 8444 KB Output is correct
3 Correct 129 ms 8748 KB Output is correct
4 Correct 44 ms 2500 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 7244 KB Output is correct
2 Correct 167 ms 7252 KB Output is correct
3 Correct 49 ms 8020 KB Output is correct
4 Correct 129 ms 8276 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 7504 KB Output is correct
2 Correct 171 ms 8920 KB Output is correct
3 Correct 168 ms 9008 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 8016 KB Output is correct