oj.uz

Submission #796956

# Submission time Handle Problem Language Result Execution time Memory
796956 2023-07-29T00:49:30 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 1772 ms 36180 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;
    left.push_back({i, seg1.query(1, n, 1, i, 1)}); right.push_back({i, seg1.query(1, n, 1, i - 1, 1)});
    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];
    }
    
    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];
    }
    
    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});
        }
    }
    if(i > 1 && seg1.query(1, n, 1, i - 1, 1) < arr[i]) range.push_back({1, i - 1});
    if(i < n && seg1.query(1, n, i + 1, n, 1) < arr[i]) range.push_back({i + 1, n});
    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);
    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) {
            seg4.erasex(1, n, a, 1);
            if(a > 1) seg4.erasex(1, n, a - 1, 1);
            if(a < n) seg4.erasex(1, n, a + 1, 1);
            
            arr[a] = b;
            seg1.update(1, n, a, b, 1);
            seg2.update(1, n, a, b, 1);
            
            update(a);
            if(a > 1) update(a - 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:182:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  182 |     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 12776 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 12 ms 12900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12768 KB Output is correct
2 Correct 496 ms 34980 KB Output is correct
3 Correct 590 ms 34552 KB Output is correct
4 Correct 497 ms 35020 KB Output is correct
5 Correct 576 ms 34512 KB Output is correct
6 Correct 237 ms 32748 KB Output is correct
7 Correct 401 ms 30240 KB Output is correct
8 Correct 235 ms 32744 KB Output is correct
9 Correct 403 ms 30148 KB Output is correct
10 Correct 479 ms 32152 KB Output is correct
11 Correct 523 ms 31024 KB Output is correct
12 Correct 267 ms 32076 KB Output is correct
13 Correct 279 ms 32076 KB Output is correct
14 Correct 279 ms 34252 KB Output is correct
15 Correct 287 ms 34332 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 12776 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 12 ms 12900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12768 KB Output is correct
2 Correct 496 ms 34980 KB Output is correct
3 Correct 590 ms 34552 KB Output is correct
4 Correct 497 ms 35020 KB Output is correct
5 Correct 576 ms 34512 KB Output is correct
6 Correct 237 ms 32748 KB Output is correct
7 Correct 401 ms 30240 KB Output is correct
8 Correct 235 ms 32744 KB Output is correct
9 Correct 403 ms 30148 KB Output is correct
10 Correct 479 ms 32152 KB Output is correct
11 Correct 523 ms 31024 KB Output is correct
12 Correct 267 ms 32076 KB Output is correct
13 Correct 279 ms 32076 KB Output is correct
14 Correct 279 ms 34252 KB Output is correct
15 Correct 287 ms 34332 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Correct 1079 ms 35012 KB Output is correct
18 Correct 837 ms 36180 KB Output is correct
19 Correct 1018 ms 35136 KB Output is correct
20 Correct 1035 ms 34704 KB Output is correct
21 Correct 992 ms 34864 KB Output is correct
22 Correct 842 ms 36044 KB Output is correct
23 Correct 950 ms 34352 KB Output is correct
24 Correct 1105 ms 35400 KB Output is correct
25 Correct 1000 ms 35248 KB Output is correct
26 Correct 1082 ms 35260 KB Output is correct
27 Correct 374 ms 33228 KB Output is correct
28 Correct 379 ms 33208 KB Output is correct
29 Correct 390 ms 33228 KB Output is correct
30 Correct 918 ms 30464 KB Output is correct
31 Correct 913 ms 30516 KB Output is correct
32 Correct 1171 ms 31912 KB Output is correct
33 Correct 777 ms 32532 KB Output is correct
34 Correct 1168 ms 30620 KB Output is correct
35 Correct 883 ms 29572 KB Output is correct
36 Correct 994 ms 32520 KB Output is correct
37 Correct 460 ms 32428 KB Output is correct
38 Correct 427 ms 32460 KB Output is correct
39 Correct 467 ms 34820 KB Output is correct
40 Correct 462 ms 34912 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12768 KB Output is correct
2 Correct 496 ms 34980 KB Output is correct
3 Correct 590 ms 34552 KB Output is correct
4 Correct 497 ms 35020 KB Output is correct
5 Correct 576 ms 34512 KB Output is correct
6 Correct 237 ms 32748 KB Output is correct
7 Correct 401 ms 30240 KB Output is correct
8 Correct 235 ms 32744 KB Output is correct
9 Correct 403 ms 30148 KB Output is correct
10 Correct 479 ms 32152 KB Output is correct
11 Correct 523 ms 31024 KB Output is correct
12 Correct 267 ms 32076 KB Output is correct
13 Correct 279 ms 32076 KB Output is correct
14 Correct 279 ms 34252 KB Output is correct
15 Correct 287 ms 34332 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Incorrect 1772 ms 35172 KB Output isn't correct
18 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 12776 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 12 ms 12900 KB Output isn't correct
6 Halted 0 ms 0 KB -