oj.uz

Submission #797119

# Submission time Handle Problem Language Result Execution time Memory
797119 2023-07-29T06:58:50 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 1731 ms 27084 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) {
            seg4.erasex(1, n, a, 1);
            
            arr[a] = b;
            seg1.update(1, n, a, b, 1);
            seg2.update(1, n, a, b, 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 9 ms 12804 KB Output is correct
4 Correct 9 ms 12760 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 8 ms 12864 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 5 ms 12860 KB Output is correct
2 Correct 367 ms 23084 KB Output is correct
3 Correct 444 ms 22628 KB Output is correct
4 Correct 356 ms 23156 KB Output is correct
5 Correct 427 ms 22640 KB Output is correct
6 Correct 101 ms 21604 KB Output is correct
7 Correct 273 ms 19416 KB Output is correct
8 Correct 103 ms 21580 KB Output is correct
9 Correct 276 ms 19584 KB Output is correct
10 Correct 360 ms 20300 KB Output is correct
11 Correct 396 ms 20168 KB Output is correct
12 Correct 140 ms 20556 KB Output is correct
13 Correct 152 ms 20556 KB Output is correct
14 Correct 151 ms 23116 KB Output is correct
15 Correct 165 ms 22924 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 9 ms 12804 KB Output is correct
4 Correct 9 ms 12760 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 8 ms 12864 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 5 ms 12860 KB Output is correct
2 Correct 367 ms 23084 KB Output is correct
3 Correct 444 ms 22628 KB Output is correct
4 Correct 356 ms 23156 KB Output is correct
5 Correct 427 ms 22640 KB Output is correct
6 Correct 101 ms 21604 KB Output is correct
7 Correct 273 ms 19416 KB Output is correct
8 Correct 103 ms 21580 KB Output is correct
9 Correct 276 ms 19584 KB Output is correct
10 Correct 360 ms 20300 KB Output is correct
11 Correct 396 ms 20168 KB Output is correct
12 Correct 140 ms 20556 KB Output is correct
13 Correct 152 ms 20556 KB Output is correct
14 Correct 151 ms 23116 KB Output is correct
15 Correct 165 ms 22924 KB Output is correct
16 Correct 12 ms 12756 KB Output is correct
17 Correct 900 ms 23448 KB Output is correct
18 Correct 713 ms 24472 KB Output is correct
19 Correct 910 ms 23808 KB Output is correct
20 Correct 934 ms 23632 KB Output is correct
21 Correct 858 ms 23612 KB Output is correct
22 Correct 733 ms 24500 KB Output is correct
23 Correct 895 ms 23268 KB Output is correct
24 Correct 999 ms 23940 KB Output is correct
25 Correct 902 ms 23844 KB Output is correct
26 Correct 1016 ms 23984 KB Output is correct
27 Correct 259 ms 22188 KB Output is correct
28 Correct 253 ms 22164 KB Output is correct
29 Correct 266 ms 22136 KB Output is correct
30 Correct 773 ms 20528 KB Output is correct
31 Correct 763 ms 20328 KB Output is correct
32 Correct 1101 ms 21272 KB Output is correct
33 Correct 647 ms 21012 KB Output is correct
34 Correct 1095 ms 20872 KB Output is correct
35 Correct 786 ms 20160 KB Output is correct
36 Correct 899 ms 21472 KB Output is correct
37 Correct 334 ms 21508 KB Output is correct
38 Correct 320 ms 21536 KB Output is correct
39 Correct 347 ms 24032 KB Output is correct
40 Correct 344 ms 23936 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12860 KB Output is correct
2 Correct 367 ms 23084 KB Output is correct
3 Correct 444 ms 22628 KB Output is correct
4 Correct 356 ms 23156 KB Output is correct
5 Correct 427 ms 22640 KB Output is correct
6 Correct 101 ms 21604 KB Output is correct
7 Correct 273 ms 19416 KB Output is correct
8 Correct 103 ms 21580 KB Output is correct
9 Correct 276 ms 19584 KB Output is correct
10 Correct 360 ms 20300 KB Output is correct
11 Correct 396 ms 20168 KB Output is correct
12 Correct 140 ms 20556 KB Output is correct
13 Correct 152 ms 20556 KB Output is correct
14 Correct 151 ms 23116 KB Output is correct
15 Correct 165 ms 22924 KB Output is correct
16 Correct 8 ms 12856 KB Output is correct
17 Correct 1731 ms 23484 KB Output is correct
18 Incorrect 1414 ms 27084 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 9 ms 12804 KB Output is correct
4 Correct 9 ms 12760 KB Output is correct
5 Correct 12 ms 12884 KB Output is correct
6 Incorrect 8 ms 12864 KB Output isn't correct
7 Halted 0 ms 0 KB -