oj.uz

Submission #320942

# Submission time Handle Problem Language Result Execution time Memory
320942 2020-11-10T10:13:31 Z TAMREF Growing Trees (BOI11_grow) C++11
100 / 100
 180 ms 5732 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct seg{
    int laz[270005], mn[270005], mx[270005];
    void init(int i, int s, int e, int *a){
        if(s == e){
            mn[i] = mx[i] = a[s];
            return;
        }
        int m = s + e >> 1;
        init(2*i, s, m, a);
        init(2*i+1, m+1, e, a);
        mn[i] = mn[2*i];
        mx[i] = mx[2*i+1];
    }
    void upd(int i, int s, int e, int l, int r, int v){
        if(i == 1){
            debug("upd %d %d %d\n",l,r,v);
        }
        if(r < s || l > e) return;
        if(l <= s && e <= r){
            laz[i] += v;
            mn[i] += v;
            mx[i] += v;
            return;
        }
        int m = s + e >> 1;
        mn[2*i] += laz[i]; mx[2*i] += laz[i]; laz[2*i] += laz[i];
        mn[2*i+1] += laz[i]; mx[2*i+1] += laz[i]; laz[2*i+1] += laz[i];
        laz[i] = 0;
        upd(2*i, s, m, l, r, v);
        upd(2*i+1, m+1, e, l, r, v);
        mn[i] = mn[2*i];
        mx[i] = mx[2*i+1];
    }
    int lowerbound(int i, int s, int e, int x){
        if(s == e){
            if(mn[i] >= x) return s;
            else return s + 1;
        }
        int m = s + e >> 1;
        if(mx[2*i] + laz[i] >= x) return lowerbound(2*i, s, m, x - laz[i]);
        else return lowerbound(2*i+1, m+1, e, x - laz[i]);
    }
    int get(int i, int s, int e, int j){
        if(s == e) return mn[i];
        int m = s + e >> 1;
        int v = -1;
        if(j <= m) v = get(2*i, s, m, j);
        else v = get(2*i+1, m+1, e, j);
        return v + laz[i];
    }
    int stat(int i, int s, int e, int l, int r){
        if(mx[i] < l || mn[i] > r) return 0;
        if(l <= mn[i] && mx[i] <= r){
            return e - s + 1;
        }
        int m = s + e >> 1;
        int lv = stat(2*i, s, m, l - laz[i], r - laz[i]);
        int rv = stat(2*i+1, m+1, e, l - laz[i], r - laz[i]);
        return lv + rv;
    }
} S;

int n, q, a[100005];

int main(){
    #ifndef TAMREF
    fio;
    #endif
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    S.init(1, 1, n, a);
    debug("init\n");
    char ty;
    for(int l, r, c, h; q--;){
        debug("query %d\n",q);
        cin >> ty;
        assert(ty == 'F' || ty == 'C');
        if(ty == 'F'){
            cin >> c >> h;
            int u = S.lowerbound(1, 1, n, h);
            debug("u = %d\n",u);
            if(u + c > n){
                S.upd(1, 1, n, u, n, 1);
                continue;
            }
            int w = S.get(1, 1, n, u + c - 1);
            debug("w = %d\n",w);
            int x = S.lowerbound(1, 1, n, w),
                y = S.lowerbound(1, 1, n, w+1);
            debug("x = %d, y = %d\n",x,y);
            int d = c - (x - u);
            S.upd(1, 1, n, u, x-1, 1);
            S.upd(1, 1, n, y-d, y-1, 1);
        }else{
            cin >> l >> r;
            cout << S.stat(1, 1, n, l, r) << '\n';
        }
        for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
    }
}

Compilation message

grow.cpp: In member function 'void seg::init(int, int, int, int*)':
grow.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m = s + e >> 1;
      |                 ~~^~~
grow.cpp: In member function 'void seg::upd(int, int, int, int, int, int)':
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:49:13: note: in expansion of macro 'debug'
   49 |             debug("upd %d %d %d\n",l,r,v);
      |             ^~~~~
grow.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m = s + e >> 1;
      |                 ~~^~~
grow.cpp: In member function 'int seg::lowerbound(int, int, int, int)':
grow.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int m = s + e >> 1;
      |                 ~~^~~
grow.cpp: In member function 'int seg::get(int, int, int, int)':
grow.cpp:78:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int m = s + e >> 1;
      |                 ~~^~~
grow.cpp: In member function 'int seg::stat(int, int, int, int, int)':
grow.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int m = s + e >> 1;
      |                 ~~^~~
grow.cpp: In function 'int main()':
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:106:5: note: in expansion of macro 'debug'
  106 |     debug("init\n");
      |     ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:109:9: note: in expansion of macro 'debug'
  109 |         debug("query %d\n",q);
      |         ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:115:13: note: in expansion of macro 'debug'
  115 |             debug("u = %d\n",u);
      |             ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:121:13: note: in expansion of macro 'debug'
  121 |             debug("w = %d\n",w);
      |             ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:124:13: note: in expansion of macro 'debug'
  124 |             debug("x = %d, y = %d\n",x,y);
      |             ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:132:37: note: in expansion of macro 'debug'
  132 |         for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
      |                                     ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
grow.cpp:132:69: note: in expansion of macro 'debug'
  132 |         for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
      |                                                                     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4068 KB Output is correct
2 Correct 124 ms 5624 KB Output is correct
3 Correct 41 ms 5604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 45 ms 1636 KB Output is correct
6 Correct 59 ms 1892 KB Output is correct
7 Correct 5 ms 620 KB Output is correct
8 Correct 22 ms 1388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1144 KB Output is correct
2 Correct 55 ms 2024 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 31 ms 1508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 996 KB Output is correct
2 Correct 59 ms 1892 KB Output is correct
3 Correct 10 ms 748 KB Output is correct
4 Correct 53 ms 2020 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2404 KB Output is correct
2 Correct 115 ms 5092 KB Output is correct
3 Correct 16 ms 1516 KB Output is correct
4 Correct 34 ms 5092 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 3940 KB Output is correct
2 Correct 113 ms 5220 KB Output is correct
3 Correct 39 ms 5348 KB Output is correct
4 Correct 16 ms 1516 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3940 KB Output is correct
2 Correct 83 ms 5220 KB Output is correct
3 Correct 41 ms 5604 KB Output is correct
4 Correct 18 ms 1516 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3940 KB Output is correct
2 Correct 118 ms 5092 KB Output is correct
3 Correct 37 ms 4588 KB Output is correct
4 Correct 60 ms 4836 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 4068 KB Output is correct
2 Correct 135 ms 5476 KB Output is correct
3 Correct 180 ms 5732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4324 KB Output is correct