oj.uz

Submission #797130

# Submission time Handle Problem Language Result Execution time Memory
797130 2023-07-29T07:05:11 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 1685 ms 25164 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
int n, q;
int arr[100005];

struct SEG1 {
    ll seg[400005];
    void update(int str, int ed, int idx, ll val, int node) {
        if(str == ed) {
            seg[node] = val;
            return;
        }
        int mid = str + ed >> 1;
        if(idx <= mid) update(str, mid, idx, val, node << 1);
        else update(mid + 1, ed, idx, val, node << 1 | 1);
        seg[node] = seg[node << 1] + seg[node << 1 | 1];
    }
    ll query(int str, int ed, int left, int right, int node) {
        if(str > right || ed < left) return 0;
        if(left <= str && ed <= right) return seg[node];
        int mid = str + ed >> 1;
        return query(str, mid, left, right, node << 1) + query(mid + 1, ed, left, right, node << 1 | 1);
    }
} seg1;

struct SEG2 {
    int seg[400005];
    void update(int str, int ed, int idx, int val, int node) {
        if(str == ed) {
            seg[node] = val;
            return;
        }
        int mid = str + ed >> 1;
        if(idx <= mid) update(str, mid, idx, val, node << 1);
        else update(mid + 1, ed, idx, val, node << 1 | 1);
        seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
    }
    int get_mx(int str, int ed, int left, int right, int val, int node) {
        if(str > right || ed < left) return -1;
        if(seg[node] <= val) return -1;
        if(str == ed) return str;
        int mid = str + ed >> 1;
        int tmp = get_mx(mid + 1, ed, left, right, val, node << 1 | 1);
        if(tmp != -1) return tmp;
        return get_mx(str, mid, left, right, val, node << 1);
    }
    int get_mn(int str, int ed, int left, int right, ll val, int node) {
        if(str > right || ed < left) return -1;
        if(seg[node] <= val) return -1;
        if(str == ed) return str;
        int mid = str + ed >> 1;
        int tmp = get_mn(str, mid, left, right, val, node << 1);
        if(tmp != -1) return tmp;
        return get_mn(mid + 1, ed, left, right, val, node << 1 | 1);
    }
} seg2;

struct SEG3 {
    struct Node{
        int mn, cnt;
        Node() { mn = inf, cnt = 0; }
    };
    Node seg[400005];
    int lazy[400005];
    Node Merge(Node l, Node r) {
        Node ret; ret.cnt = 0;
        ret.mn = min(l.mn, r.mn);
        if(l.mn == ret.mn) ret.cnt += l.cnt;
        if(r.mn == ret.mn) ret.cnt += r.cnt;
        return ret;
    }
    void init(int str, int ed, int node) {
        lazy[node] = 0;
        if(str == ed) {
            seg[node].mn = 0, seg[node].cnt = 1;
            return;
        }
        int mid = str + ed >> 1;
        init(str, mid, node << 1);
        init(mid + 1, ed, node << 1 | 1);
        seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
    }
    void lazyProp(int str, int ed, int node) {
        if(lazy[node]) {
            seg[node].mn += lazy[node];
            if(str != ed) {
                lazy[node << 1] += lazy[node];
                lazy[node << 1 | 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    void update(int str, int ed, int left, int right, int val, int node) {
        lazyProp(str, ed, node);
        if(str > right || ed < left) return;
        if(left <= str && ed <= right) {
            lazy[node] += val;
            lazyProp(str, ed, node);
            return;
        }
        int mid = str + ed >> 1;
        update(str, mid, left, right, val, node << 1);
        update(mid + 1, ed, left, right, val, node << 1 | 1);
        seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
    }
    Node query(int str, int ed, int left, int right, int node) {
        lazyProp(str, ed, node);
        if(str > right || ed < left) return Node();
        if(left <= str && ed <= right) return seg[node];
        int mid = str + ed >> 1;
        return Merge(query(str, mid, left, right, node << 1), query(mid + 1, ed, left, right, node << 1 | 1));
    }
} seg3;

set<pii> s;
struct SEG4 {
    vector<pii> seg[400005];
    void update(int str, int ed, int l, int r, int node) {
        int mid = str + ed >> 1;
        if(str == ed || (l <= mid && r > mid)) {
            seg[node].push_back({l, r});
            seg3.update(1, n, l, r, 1, 1);
            return;
        }
        if(r <= mid) update(str, mid, l, r, node << 1);
        else update(mid + 1, ed, l, r, node << 1 | 1);
    }
    
    void erasex(int str, int ed, int x, int node) {
        while(!seg[node].empty() && seg[node].back().first <= x && x <= seg[node].back().second) {
            seg3.update(1, n, seg[node].back().first, seg[node].back().second, -1, 1);
            s.erase({seg[node].back().first, seg[node].back().second});
            seg[node].pop_back();
        }
        if(str == ed) return;
        int mid = str + ed >> 1;
        if(x <= mid) erasex(str, mid, x, node << 1);
        else erasex(mid + 1, ed, x, node << 1 | 1);
    }
} seg4;

void update(int i) {
    vector<pll> left, right;
    int j = i, sum = arr[j];
    while(j > 1) {
        j = seg2.get_mx(1, n, 1, j - 1, sum, 1);
        if(j == -1) break;
        left.push_back({j, seg1.query(1, n, 1, j, 1)});
        sum += arr[j];
    }
    if(i == 1) left.push_back({0, 0});
    
    j = i, sum = arr[j];
    while(j < n) {
        j = seg2.get_mn(1, n, j + 1, n, sum, 1);
        if(j == -1) break;
        right.push_back({j, seg1.query(1, n, 1, j - 1, 1)});
        sum += arr[j];
    }
    if(i == n) right.push_back({n + 1, seg1.query(1, n, 1, n, 1)});
    
    vector<pii> range;
    for(auto l : left) for(auto r : right) {
        if(r.second - l.second < min(arr[r.first], arr[l.first])) {
            range.push_back({l.first + 1, r.first - 1});
        }
    }
    sort(range.begin(), range.end(), [&](auto a, auto b) {
            return a.second - a.first < b.second - b.first;
        });
    
    for(auto [l, r] : range) {
        if(s.find({l, r}) == s.end()) {
            seg4.update(1, n, l, r, 1);
            s.insert({l, r});
        }
    }
}

int compL(int i, int lim) {
    vector<int> right;
    int j = i, sum = arr[j];
    while(j < n) {
        j = seg2.get_mn(1, n, j + 1, n, sum, 1);
        if(j == -1) break;
        right.push_back(j);
        sum += arr[j];
    }
    int mx = i;
    for(auto r : right) {
        if(r <= lim && seg1.query(1, n, i, r - 1, 1) < arr[r]) mx = max(mx, r);
    }
    return mx;
}

int compR(int i, int lim) {
    vector<int> left;
    int j = i, sum = arr[j];
    while(j > 1) {
        j = seg2.get_mx(1, n, 1, j - 1, sum, 1);
        if(j == -1) break;
        left.push_back(j);
        sum += arr[j];
    }
    int mn = i;
    for(auto l : left) {
        if(l >= lim && seg1.query(1, n, l + 1, i, 1) < arr[l]) mn = min(mn, l);
    }
    return mn;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n; seg3.init(1, n, 1); arr[0] = arr[n + 1] = inf;
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    for(int i = 1; i <= n; ++i) seg1.update(1, n, i, arr[i], 1);
    for(int i = 1; i <= n; ++i) seg2.update(1, n, i, arr[i], 1);
    for(int i = 1; i <= n; ++i) update(i);
    
    cin >> q;
    while(q--) {
        int t, a, b; cin >> t >> a >> b;
        if(t == 1) {
            arr[a] = b;
            seg1.update(1, n, a, b, 1);
            seg2.update(1, n, a, b, 1);
            
            seg4.erasex(1, n, a, 1);
            update(a);
            
            if(a > 1) seg4.erasex(1, n, a - 1, 1);
            if(a > 1) update(a - 1);
            
            if(a < n) seg4.erasex(1, n, a + 1, 1);
            if(a < n) update(a + 1);
        }
        else {
            int l = a, r = b;
            a = compL(a, r); b = compR(b, l);
            cout << seg3.query(1, n, a, b, 1).cnt << '\n';
        }
    }
    return 0;
}

Compilation message

fish2.cpp: In member function 'void SEG1::update(int, int, int, ll, int)':
fish2.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'll SEG1::query(int, int, int, int, int)':
fish2.cpp:30:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG2::update(int, int, int, int, int)':
fish2.cpp:42:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mx(int, int, int, int, int, int)':
fish2.cpp:51:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mn(int, int, int, int, ll, int)':
fish2.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG3::init(int, int, int)':
fish2.cpp:87:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG3::update(int, int, int, int, int, int)':
fish2.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'SEG3::Node SEG3::query(int, int, int, int, int)':
fish2.cpp:119:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG4::update(int, int, int, int, int)':
fish2.cpp:128:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG4::erasex(int, int, int, int)':
fish2.cpp:145:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In function 'void update(int)':
fish2.cpp:181:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |     for(auto [l, r] : range) {
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 9 ms 12912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 342 ms 22536 KB Output is correct
3 Correct 436 ms 22268 KB Output is correct
4 Correct 338 ms 22568 KB Output is correct
5 Correct 422 ms 22340 KB Output is correct
6 Correct 101 ms 20624 KB Output is correct
7 Correct 275 ms 19288 KB Output is correct
8 Correct 124 ms 20684 KB Output is correct
9 Correct 277 ms 19288 KB Output is correct
10 Correct 339 ms 19708 KB Output is correct
11 Correct 391 ms 19968 KB Output is correct
12 Correct 134 ms 20304 KB Output is correct
13 Correct 147 ms 20296 KB Output is correct
14 Correct 140 ms 22496 KB Output is correct
15 Correct 151 ms 22312 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 9 ms 12912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 342 ms 22536 KB Output is correct
3 Correct 436 ms 22268 KB Output is correct
4 Correct 338 ms 22568 KB Output is correct
5 Correct 422 ms 22340 KB Output is correct
6 Correct 101 ms 20624 KB Output is correct
7 Correct 275 ms 19288 KB Output is correct
8 Correct 124 ms 20684 KB Output is correct
9 Correct 277 ms 19288 KB Output is correct
10 Correct 339 ms 19708 KB Output is correct
11 Correct 391 ms 19968 KB Output is correct
12 Correct 134 ms 20304 KB Output is correct
13 Correct 147 ms 20296 KB Output is correct
14 Correct 140 ms 22496 KB Output is correct
15 Correct 151 ms 22312 KB Output is correct
16 Correct 7 ms 12756 KB Output is correct
17 Correct 879 ms 22612 KB Output is correct
18 Correct 693 ms 23704 KB Output is correct
19 Correct 876 ms 22924 KB Output is correct
20 Correct 887 ms 22784 KB Output is correct
21 Correct 835 ms 22668 KB Output is correct
22 Correct 694 ms 23620 KB Output is correct
23 Correct 813 ms 22476 KB Output is correct
24 Correct 928 ms 23100 KB Output is correct
25 Correct 839 ms 22884 KB Output is correct
26 Correct 934 ms 23208 KB Output is correct
27 Correct 247 ms 21244 KB Output is correct
28 Correct 242 ms 21276 KB Output is correct
29 Correct 250 ms 21324 KB Output is correct
30 Correct 751 ms 19576 KB Output is correct
31 Correct 758 ms 19524 KB Output is correct
32 Correct 1034 ms 20476 KB Output is correct
33 Correct 624 ms 20172 KB Output is correct
34 Correct 1049 ms 19688 KB Output is correct
35 Correct 752 ms 19160 KB Output is correct
36 Correct 863 ms 20556 KB Output is correct
37 Correct 325 ms 20660 KB Output is correct
38 Correct 292 ms 20644 KB Output is correct
39 Correct 341 ms 23116 KB Output is correct
40 Correct 328 ms 22852 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 342 ms 22536 KB Output is correct
3 Correct 436 ms 22268 KB Output is correct
4 Correct 338 ms 22568 KB Output is correct
5 Correct 422 ms 22340 KB Output is correct
6 Correct 101 ms 20624 KB Output is correct
7 Correct 275 ms 19288 KB Output is correct
8 Correct 124 ms 20684 KB Output is correct
9 Correct 277 ms 19288 KB Output is correct
10 Correct 339 ms 19708 KB Output is correct
11 Correct 391 ms 19968 KB Output is correct
12 Correct 134 ms 20304 KB Output is correct
13 Correct 147 ms 20296 KB Output is correct
14 Correct 140 ms 22496 KB Output is correct
15 Correct 151 ms 22312 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Correct 1685 ms 22636 KB Output is correct
18 Incorrect 1382 ms 25164 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 9 ms 12912 KB Output isn't correct
7 Halted 0 ms 0 KB -