oj.uz

Submission #797189

# Submission time Handle Problem Language Result Execution time Memory
797189 2023-07-29T07:44:59 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 2883 ms 45624 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1000000001)
 
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)) {
            assert(seg[node].empty() || (seg[node].back().first >= l && seg[node].back().second <= r));
            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];
    }
    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];
    }
    right.push_back({n + 1, seg1.query(1, n, 1, n, 1)});
    
    vector<pii> range;
    for(auto l : left) for(auto r : right) {
        if(l.first == 0 && r.first == n + 1) continue;
        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) {
            if(a.second - a.first != b.second - b.first) return a.second - a.first < b.second - b.first;
            return a.first < 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;
}

void update_query(int a, int b) {
    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);
}

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];
        update_query(i, arr[i]);
    }
    
    cin >> q;
    while(q--) {
        int t, a, b; cin >> t >> a >> b;
        if(t == 1) update_query(a, b);
        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:146:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In function 'void update(int)':
fish2.cpp:185:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  185 |     for(auto [l, r] : range) {
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12808 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 7 ms 12836 KB Output is correct
5 Correct 20 ms 12900 KB Output is correct
6 Correct 10 ms 12912 KB Output is correct
7 Runtime error 33 ms 26020 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 485 ms 22472 KB Output is correct
3 Correct 936 ms 22364 KB Output is correct
4 Correct 503 ms 22576 KB Output is correct
5 Correct 906 ms 22292 KB Output is correct
6 Correct 358 ms 20644 KB Output is correct
7 Correct 1052 ms 19328 KB Output is correct
8 Correct 376 ms 20856 KB Output is correct
9 Correct 1160 ms 19340 KB Output is correct
10 Correct 1866 ms 19840 KB Output is correct
11 Correct 2230 ms 19776 KB Output is correct
12 Correct 628 ms 20528 KB Output is correct
13 Correct 592 ms 20280 KB Output is correct
14 Correct 498 ms 22476 KB Output is correct
15 Correct 526 ms 22252 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12808 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 7 ms 12836 KB Output is correct
5 Correct 20 ms 12900 KB Output is correct
6 Correct 10 ms 12912 KB Output is correct
7 Runtime error 33 ms 26020 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 485 ms 22472 KB Output is correct
3 Correct 936 ms 22364 KB Output is correct
4 Correct 503 ms 22576 KB Output is correct
5 Correct 906 ms 22292 KB Output is correct
6 Correct 358 ms 20644 KB Output is correct
7 Correct 1052 ms 19328 KB Output is correct
8 Correct 376 ms 20856 KB Output is correct
9 Correct 1160 ms 19340 KB Output is correct
10 Correct 1866 ms 19840 KB Output is correct
11 Correct 2230 ms 19776 KB Output is correct
12 Correct 628 ms 20528 KB Output is correct
13 Correct 592 ms 20280 KB Output is correct
14 Correct 498 ms 22476 KB Output is correct
15 Correct 526 ms 22252 KB Output is correct
16 Correct 5 ms 12756 KB Output is correct
17 Correct 1392 ms 22884 KB Output is correct
18 Correct 803 ms 24756 KB Output is correct
19 Correct 1372 ms 23820 KB Output is correct
20 Correct 1425 ms 23736 KB Output is correct
21 Correct 1380 ms 23588 KB Output is correct
22 Correct 851 ms 24724 KB Output is correct
23 Correct 1331 ms 23352 KB Output is correct
24 Correct 1462 ms 23992 KB Output is correct
25 Correct 1379 ms 23840 KB Output is correct
26 Correct 1472 ms 23920 KB Output is correct
27 Correct 510 ms 22856 KB Output is correct
28 Correct 507 ms 22812 KB Output is correct
29 Correct 502 ms 22860 KB Output is correct
30 Correct 1704 ms 20276 KB Output is correct
31 Correct 1588 ms 20404 KB Output is correct
32 Correct 2844 ms 21228 KB Output is correct
33 Correct 2189 ms 21256 KB Output is correct
34 Correct 2883 ms 20528 KB Output is correct
35 Correct 2585 ms 20048 KB Output is correct
36 Correct 2510 ms 21684 KB Output is correct
37 Correct 767 ms 21328 KB Output is correct
38 Correct 757 ms 21368 KB Output is correct
39 Correct 708 ms 24244 KB Output is correct
40 Correct 774 ms 23984 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 485 ms 22472 KB Output is correct
3 Correct 936 ms 22364 KB Output is correct
4 Correct 503 ms 22576 KB Output is correct
5 Correct 906 ms 22292 KB Output is correct
6 Correct 358 ms 20644 KB Output is correct
7 Correct 1052 ms 19328 KB Output is correct
8 Correct 376 ms 20856 KB Output is correct
9 Correct 1160 ms 19340 KB Output is correct
10 Correct 1866 ms 19840 KB Output is correct
11 Correct 2230 ms 19776 KB Output is correct
12 Correct 628 ms 20528 KB Output is correct
13 Correct 592 ms 20280 KB Output is correct
14 Correct 498 ms 22476 KB Output is correct
15 Correct 526 ms 22252 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Runtime error 500 ms 45624 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12808 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 7 ms 12836 KB Output is correct
5 Correct 20 ms 12900 KB Output is correct
6 Correct 10 ms 12912 KB Output is correct
7 Runtime error 33 ms 26020 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -