oj.uz

Submission #797191

# Submission time Handle Problem Language Result Execution time Memory
797191 2023-07-29T07:49:08 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 2888 ms 45504 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 < (ll)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) < (ll)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) < (ll)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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12832 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 15 ms 12924 KB Output is correct
6 Correct 10 ms 12884 KB Output is correct
7 Runtime error 20 ms 25940 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 12756 KB Output is correct
2 Correct 476 ms 22552 KB Output is correct
3 Correct 939 ms 22268 KB Output is correct
4 Correct 477 ms 22544 KB Output is correct
5 Correct 902 ms 22220 KB Output is correct
6 Correct 355 ms 20684 KB Output is correct
7 Correct 1057 ms 19352 KB Output is correct
8 Correct 353 ms 20684 KB Output is correct
9 Correct 1134 ms 19304 KB Output is correct
10 Correct 1874 ms 19756 KB Output is correct
11 Correct 2221 ms 19916 KB Output is correct
12 Correct 622 ms 20372 KB Output is correct
13 Correct 593 ms 20352 KB Output is correct
14 Correct 519 ms 22604 KB Output is correct
15 Correct 522 ms 22332 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 12832 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 15 ms 12924 KB Output is correct
6 Correct 10 ms 12884 KB Output is correct
7 Runtime error 20 ms 25940 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 12756 KB Output is correct
2 Correct 476 ms 22552 KB Output is correct
3 Correct 939 ms 22268 KB Output is correct
4 Correct 477 ms 22544 KB Output is correct
5 Correct 902 ms 22220 KB Output is correct
6 Correct 355 ms 20684 KB Output is correct
7 Correct 1057 ms 19352 KB Output is correct
8 Correct 353 ms 20684 KB Output is correct
9 Correct 1134 ms 19304 KB Output is correct
10 Correct 1874 ms 19756 KB Output is correct
11 Correct 2221 ms 19916 KB Output is correct
12 Correct 622 ms 20372 KB Output is correct
13 Correct 593 ms 20352 KB Output is correct
14 Correct 519 ms 22604 KB Output is correct
15 Correct 522 ms 22332 KB Output is correct
16 Correct 6 ms 12864 KB Output is correct
17 Correct 1376 ms 22676 KB Output is correct
18 Correct 802 ms 23588 KB Output is correct
19 Correct 1342 ms 22804 KB Output is correct
20 Correct 1392 ms 22740 KB Output is correct
21 Correct 1383 ms 22792 KB Output is correct
22 Correct 805 ms 23760 KB Output is correct
23 Correct 1308 ms 22372 KB Output is correct
24 Correct 1476 ms 23016 KB Output is correct
25 Correct 1346 ms 22908 KB Output is correct
26 Correct 1443 ms 23024 KB Output is correct
27 Correct 507 ms 21312 KB Output is correct
28 Correct 498 ms 21204 KB Output is correct
29 Correct 507 ms 21268 KB Output is correct
30 Correct 1703 ms 19512 KB Output is correct
31 Correct 1574 ms 19572 KB Output is correct
32 Correct 2832 ms 20376 KB Output is correct
33 Correct 2208 ms 20260 KB Output is correct
34 Correct 2888 ms 19744 KB Output is correct
35 Correct 2579 ms 19148 KB Output is correct
36 Correct 2482 ms 20604 KB Output is correct
37 Correct 770 ms 20776 KB Output is correct
38 Correct 758 ms 20556 KB Output is correct
39 Correct 701 ms 23088 KB Output is correct
40 Correct 698 ms 22872 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 476 ms 22552 KB Output is correct
3 Correct 939 ms 22268 KB Output is correct
4 Correct 477 ms 22544 KB Output is correct
5 Correct 902 ms 22220 KB Output is correct
6 Correct 355 ms 20684 KB Output is correct
7 Correct 1057 ms 19352 KB Output is correct
8 Correct 353 ms 20684 KB Output is correct
9 Correct 1134 ms 19304 KB Output is correct
10 Correct 1874 ms 19756 KB Output is correct
11 Correct 2221 ms 19916 KB Output is correct
12 Correct 622 ms 20372 KB Output is correct
13 Correct 593 ms 20352 KB Output is correct
14 Correct 519 ms 22604 KB Output is correct
15 Correct 522 ms 22332 KB Output is correct
16 Correct 6 ms 12852 KB Output is correct
17 Runtime error 500 ms 45504 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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12832 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 15 ms 12924 KB Output is correct
6 Correct 10 ms 12884 KB Output is correct
7 Runtime error 20 ms 25940 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -