oj.uz

Submission #568855

# Submission time Handle Problem Language Result Execution time Memory
568855 2022-05-26T09:37:21 Z maomao90 Fish 2 (JOI22_fish2) C++17
13 / 100
 4000 ms 5896 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;

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:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:50:5: note: in expansion of macro 'MLR'
   50 |     MLR;
      |     ^~~
fish2.cpp: In function 'll qsm(int, int, int, int, int)':
fish2.cpp:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:63:5: note: in expansion of macro 'MLR'
   63 |     MLR;
      |     ^~~
fish2.cpp: In function 'ii qmx(int, int, int, int, int)':
fish2.cpp:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:77:5: note: in expansion of macro 'MLR'
   77 |     MLR;
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 424 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 14 ms 368 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 5100 KB Output is correct
3 Correct 24 ms 5044 KB Output is correct
4 Correct 26 ms 5400 KB Output is correct
5 Correct 22 ms 5160 KB Output is correct
6 Correct 43 ms 5708 KB Output is correct
7 Correct 19 ms 4940 KB Output is correct
8 Correct 45 ms 5720 KB Output is correct
9 Correct 20 ms 4996 KB Output is correct
10 Correct 27 ms 5372 KB Output is correct
11 Correct 21 ms 5068 KB Output is correct
12 Correct 23 ms 4996 KB Output is correct
13 Correct 22 ms 5052 KB Output is correct
14 Correct 37 ms 5480 KB Output is correct
15 Correct 36 ms 5568 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 424 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 14 ms 368 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 27 ms 5100 KB Output is correct
23 Correct 24 ms 5044 KB Output is correct
24 Correct 26 ms 5400 KB Output is correct
25 Correct 22 ms 5160 KB Output is correct
26 Correct 43 ms 5708 KB Output is correct
27 Correct 19 ms 4940 KB Output is correct
28 Correct 45 ms 5720 KB Output is correct
29 Correct 20 ms 4996 KB Output is correct
30 Correct 27 ms 5372 KB Output is correct
31 Correct 21 ms 5068 KB Output is correct
32 Correct 23 ms 4996 KB Output is correct
33 Correct 22 ms 5052 KB Output is correct
34 Correct 37 ms 5480 KB Output is correct
35 Correct 36 ms 5568 KB Output is correct
36 Correct 375 ms 5488 KB Output is correct
37 Correct 219 ms 5164 KB Output is correct
38 Correct 124 ms 5172 KB Output is correct
39 Correct 174 ms 5452 KB Output is correct
40 Correct 123 ms 5164 KB Output is correct
41 Execution timed out 4089 ms 5836 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 5100 KB Output is correct
3 Correct 24 ms 5044 KB Output is correct
4 Correct 26 ms 5400 KB Output is correct
5 Correct 22 ms 5160 KB Output is correct
6 Correct 43 ms 5708 KB Output is correct
7 Correct 19 ms 4940 KB Output is correct
8 Correct 45 ms 5720 KB Output is correct
9 Correct 20 ms 4996 KB Output is correct
10 Correct 27 ms 5372 KB Output is correct
11 Correct 21 ms 5068 KB Output is correct
12 Correct 23 ms 4996 KB Output is correct
13 Correct 22 ms 5052 KB Output is correct
14 Correct 37 ms 5480 KB Output is correct
15 Correct 36 ms 5568 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4070 ms 5896 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 5100 KB Output is correct
3 Correct 24 ms 5044 KB Output is correct
4 Correct 26 ms 5400 KB Output is correct
5 Correct 22 ms 5160 KB Output is correct
6 Correct 43 ms 5708 KB Output is correct
7 Correct 19 ms 4940 KB Output is correct
8 Correct 45 ms 5720 KB Output is correct
9 Correct 20 ms 4996 KB Output is correct
10 Correct 27 ms 5372 KB Output is correct
11 Correct 21 ms 5068 KB Output is correct
12 Correct 23 ms 4996 KB Output is correct
13 Correct 22 ms 5052 KB Output is correct
14 Correct 37 ms 5480 KB Output is correct
15 Correct 36 ms 5568 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4032 ms 5572 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 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 424 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 14 ms 368 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 27 ms 5100 KB Output is correct
23 Correct 24 ms 5044 KB Output is correct
24 Correct 26 ms 5400 KB Output is correct
25 Correct 22 ms 5160 KB Output is correct
26 Correct 43 ms 5708 KB Output is correct
27 Correct 19 ms 4940 KB Output is correct
28 Correct 45 ms 5720 KB Output is correct
29 Correct 20 ms 4996 KB Output is correct
30 Correct 27 ms 5372 KB Output is correct
31 Correct 21 ms 5068 KB Output is correct
32 Correct 23 ms 4996 KB Output is correct
33 Correct 22 ms 5052 KB Output is correct
34 Correct 37 ms 5480 KB Output is correct
35 Correct 36 ms 5568 KB Output is correct
36 Correct 375 ms 5488 KB Output is correct
37 Correct 219 ms 5164 KB Output is correct
38 Correct 124 ms 5172 KB Output is correct
39 Correct 174 ms 5452 KB Output is correct
40 Correct 123 ms 5164 KB Output is correct
41 Execution timed out 4089 ms 5836 KB Time limit exceeded
42 Halted 0 ms 0 KB -