oj.uz

Submission #796953

# Submission time Handle Problem Language Result Execution time Memory
796953 2023-07-29T00:40:27 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 1536 ms 23768 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];
    }
    
    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) {
            if(a.first != b.first) return a.first >= b.first;
            else return a.second <= b.second;
        });
    
    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 12772 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 10 ms 12884 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 9 ms 12756 KB Output is correct
2 Correct 367 ms 22536 KB Output is correct
3 Correct 459 ms 22172 KB Output is correct
4 Correct 368 ms 22476 KB Output is correct
5 Correct 454 ms 22192 KB Output is correct
6 Correct 122 ms 20672 KB Output is correct
7 Correct 297 ms 19288 KB Output is correct
8 Correct 118 ms 20728 KB Output is correct
9 Correct 293 ms 19264 KB Output is correct
10 Correct 362 ms 19664 KB Output is correct
11 Correct 421 ms 19808 KB Output is correct
12 Correct 162 ms 20292 KB Output is correct
13 Correct 167 ms 20280 KB Output is correct
14 Correct 165 ms 22684 KB Output is correct
15 Correct 163 ms 22328 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 12772 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 10 ms 12884 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 9 ms 12756 KB Output is correct
2 Correct 367 ms 22536 KB Output is correct
3 Correct 459 ms 22172 KB Output is correct
4 Correct 368 ms 22476 KB Output is correct
5 Correct 454 ms 22192 KB Output is correct
6 Correct 122 ms 20672 KB Output is correct
7 Correct 297 ms 19288 KB Output is correct
8 Correct 118 ms 20728 KB Output is correct
9 Correct 293 ms 19264 KB Output is correct
10 Correct 362 ms 19664 KB Output is correct
11 Correct 421 ms 19808 KB Output is correct
12 Correct 162 ms 20292 KB Output is correct
13 Correct 167 ms 20280 KB Output is correct
14 Correct 165 ms 22684 KB Output is correct
15 Correct 163 ms 22328 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Correct 924 ms 22680 KB Output is correct
18 Correct 725 ms 23600 KB Output is correct
19 Correct 892 ms 22856 KB Output is correct
20 Correct 941 ms 22704 KB Output is correct
21 Correct 887 ms 22632 KB Output is correct
22 Correct 722 ms 23768 KB Output is correct
23 Correct 849 ms 22496 KB Output is correct
24 Correct 975 ms 23104 KB Output is correct
25 Correct 889 ms 23044 KB Output is correct
26 Correct 996 ms 23060 KB Output is correct
27 Correct 263 ms 21188 KB Output is correct
28 Correct 287 ms 21244 KB Output is correct
29 Correct 266 ms 21304 KB Output is correct
30 Correct 806 ms 19520 KB Output is correct
31 Correct 817 ms 19528 KB Output is correct
32 Correct 1123 ms 20380 KB Output is correct
33 Correct 664 ms 20132 KB Output is correct
34 Correct 1111 ms 19620 KB Output is correct
35 Correct 810 ms 19164 KB Output is correct
36 Correct 917 ms 20460 KB Output is correct
37 Correct 351 ms 20636 KB Output is correct
38 Correct 322 ms 20664 KB Output is correct
39 Correct 358 ms 23124 KB Output is correct
40 Correct 365 ms 22900 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12756 KB Output is correct
2 Correct 367 ms 22536 KB Output is correct
3 Correct 459 ms 22172 KB Output is correct
4 Correct 368 ms 22476 KB Output is correct
5 Correct 454 ms 22192 KB Output is correct
6 Correct 122 ms 20672 KB Output is correct
7 Correct 297 ms 19288 KB Output is correct
8 Correct 118 ms 20728 KB Output is correct
9 Correct 293 ms 19264 KB Output is correct
10 Correct 362 ms 19664 KB Output is correct
11 Correct 421 ms 19808 KB Output is correct
12 Correct 162 ms 20292 KB Output is correct
13 Correct 167 ms 20280 KB Output is correct
14 Correct 165 ms 22684 KB Output is correct
15 Correct 163 ms 22328 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Incorrect 1536 ms 22736 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 12772 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Incorrect 10 ms 12884 KB Output isn't correct
6 Halted 0 ms 0 KB -