oj.uz

Submission #568860

# Submission time Handle Problem Language Result Execution time Memory
568860 2022-05-26T09:39:31 Z maomao90 Fish 2 (JOI22_fish2) C++17
13 / 100
 4000 ms 5192 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;

int n;
int a[MAXN];
int q;

ll sm[MAXN * 4];
ii mx[MAXN * 4];
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
void upd(int i, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        sm[u] = x;
        mx[u] = {x, lo};
        return;
    }
    MLR;
    if (i <= mid) {
        upd(i, x, lc, lo, mid);
    } else {
        upd(i, x, rc, mid + 1, hi);
    }
    sm[u] = sm[lc] + sm[rc];
    mx[u] = max(mx[lc], mx[rc]);
}
ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return sm[u];
    }
    MLR;
    ll res = 0;
    if (s <= mid) {
        res += qsm(s, e, lc, lo, mid);
    }
    if (e > mid) {
        res += qsm(s, e, rc, mid + 1, hi);
    }
    return res;
}
ii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return mx[u];
    }
    MLR;
    ii res = {-1, -1};
    if (s <= mid) {
        mxto(res, qmx(s, e, lc, lo, mid));
    }
    if (e > mid) {
        mxto(res, qmx(s, e, rc, mid + 1, hi));
    }
    return res;
}

int ans;
void solve(int l, int r, int big = 0) {
    if (l > r) {
        return;
    }
    ll sm = qsm(l, r);
    ii mx = qmx(l, r);
    //cerr << l << ' ' << r << ' ' << sm << ' ' << mx.FI << ' ' << mx.SE << '\n';
    if (sm < big) {
        return;
    }
    ans++;
    solve(l, mx.SE - 1, mx.FI);
    solve(mx.SE + 1, r, mx.FI);
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    REP (i, 1, n + 1) {
        cin >> a[i];
        upd(i, a[i]);
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y;
            upd(x, y);
            a[x] = y;
        } else {
            int l, r; cin >> l >> r;
            ans = 0;
            solve(l, r);
            cout << ans << '\n';
        }
    }
    return 0;
}

Compilation message

fish2.cpp: In function 'void upd(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:53:5: note: in expansion of macro 'MLR'
   53 |     MLR;
      |     ^~~
fish2.cpp: In function 'll qsm(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:66:5: note: in expansion of macro 'MLR'
   66 |     MLR;
      |     ^~~
fish2.cpp: In function 'ii qmx(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:80:5: note: in expansion of macro 'MLR'
   80 |     MLR;
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 14 ms 360 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 364 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 16 ms 360 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 26 ms 4784 KB Output is correct
3 Correct 33 ms 4728 KB Output is correct
4 Correct 26 ms 4820 KB Output is correct
5 Correct 26 ms 4760 KB Output is correct
6 Correct 54 ms 4820 KB Output is correct
7 Correct 29 ms 4736 KB Output is correct
8 Correct 64 ms 4724 KB Output is correct
9 Correct 19 ms 4772 KB Output is correct
10 Correct 28 ms 4728 KB Output is correct
11 Correct 20 ms 4796 KB Output is correct
12 Correct 21 ms 4720 KB Output is correct
13 Correct 20 ms 4820 KB Output is correct
14 Correct 38 ms 5192 KB Output is correct
15 Correct 41 ms 5156 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 14 ms 360 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 364 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 16 ms 360 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 26 ms 4784 KB Output is correct
23 Correct 33 ms 4728 KB Output is correct
24 Correct 26 ms 4820 KB Output is correct
25 Correct 26 ms 4760 KB Output is correct
26 Correct 54 ms 4820 KB Output is correct
27 Correct 29 ms 4736 KB Output is correct
28 Correct 64 ms 4724 KB Output is correct
29 Correct 19 ms 4772 KB Output is correct
30 Correct 28 ms 4728 KB Output is correct
31 Correct 20 ms 4796 KB Output is correct
32 Correct 21 ms 4720 KB Output is correct
33 Correct 20 ms 4820 KB Output is correct
34 Correct 38 ms 5192 KB Output is correct
35 Correct 41 ms 5156 KB Output is correct
36 Correct 462 ms 5008 KB Output is correct
37 Correct 181 ms 4816 KB Output is correct
38 Correct 128 ms 4820 KB Output is correct
39 Correct 285 ms 4920 KB Output is correct
40 Correct 163 ms 4820 KB Output is correct
41 Execution timed out 4064 ms 4820 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 26 ms 4784 KB Output is correct
3 Correct 33 ms 4728 KB Output is correct
4 Correct 26 ms 4820 KB Output is correct
5 Correct 26 ms 4760 KB Output is correct
6 Correct 54 ms 4820 KB Output is correct
7 Correct 29 ms 4736 KB Output is correct
8 Correct 64 ms 4724 KB Output is correct
9 Correct 19 ms 4772 KB Output is correct
10 Correct 28 ms 4728 KB Output is correct
11 Correct 20 ms 4796 KB Output is correct
12 Correct 21 ms 4720 KB Output is correct
13 Correct 20 ms 4820 KB Output is correct
14 Correct 38 ms 5192 KB Output is correct
15 Correct 41 ms 5156 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4042 ms 5056 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 26 ms 4784 KB Output is correct
3 Correct 33 ms 4728 KB Output is correct
4 Correct 26 ms 4820 KB Output is correct
5 Correct 26 ms 4760 KB Output is correct
6 Correct 54 ms 4820 KB Output is correct
7 Correct 29 ms 4736 KB Output is correct
8 Correct 64 ms 4724 KB Output is correct
9 Correct 19 ms 4772 KB Output is correct
10 Correct 28 ms 4728 KB Output is correct
11 Correct 20 ms 4796 KB Output is correct
12 Correct 21 ms 4720 KB Output is correct
13 Correct 20 ms 4820 KB Output is correct
14 Correct 38 ms 5192 KB Output is correct
15 Correct 41 ms 5156 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Execution timed out 4094 ms 4816 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 14 ms 360 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 364 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 16 ms 360 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 26 ms 4784 KB Output is correct
23 Correct 33 ms 4728 KB Output is correct
24 Correct 26 ms 4820 KB Output is correct
25 Correct 26 ms 4760 KB Output is correct
26 Correct 54 ms 4820 KB Output is correct
27 Correct 29 ms 4736 KB Output is correct
28 Correct 64 ms 4724 KB Output is correct
29 Correct 19 ms 4772 KB Output is correct
30 Correct 28 ms 4728 KB Output is correct
31 Correct 20 ms 4796 KB Output is correct
32 Correct 21 ms 4720 KB Output is correct
33 Correct 20 ms 4820 KB Output is correct
34 Correct 38 ms 5192 KB Output is correct
35 Correct 41 ms 5156 KB Output is correct
36 Correct 462 ms 5008 KB Output is correct
37 Correct 181 ms 4816 KB Output is correct
38 Correct 128 ms 4820 KB Output is correct
39 Correct 285 ms 4920 KB Output is correct
40 Correct 163 ms 4820 KB Output is correct
41 Execution timed out 4064 ms 4820 KB Time limit exceeded
42 Halted 0 ms 0 KB -