oj.uz

Submission #796961

# Submission time Handle Problem Language Result Execution time Memory
796961 2023-07-29T01:26:12 Z eltu0815 Fish 2 (JOI22_fish2) C++14
31 / 100
 1961 ms 23624 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];
    }
    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) {
            return a.second - a.first < b.second - b.first;
        });
    
    for(auto [l, r] : range) {
        if(s.find({l, r}) == s.end()) {
            //cout << i << ' ' <<  l <<' ' << r << '\n';
            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);
            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 12792 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Incorrect 12 ms 12924 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 12756 KB Output is correct
2 Correct 356 ms 22544 KB Output is correct
3 Correct 443 ms 22260 KB Output is correct
4 Correct 351 ms 22532 KB Output is correct
5 Correct 436 ms 22268 KB Output is correct
6 Correct 106 ms 20684 KB Output is correct
7 Correct 281 ms 19216 KB Output is correct
8 Correct 107 ms 20712 KB Output is correct
9 Correct 288 ms 19268 KB Output is correct
10 Correct 351 ms 19644 KB Output is correct
11 Correct 401 ms 19836 KB Output is correct
12 Correct 140 ms 20300 KB Output is correct
13 Correct 153 ms 20348 KB Output is correct
14 Correct 145 ms 22500 KB Output is correct
15 Correct 151 ms 22316 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 12792 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Incorrect 12 ms 12924 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 12756 KB Output is correct
2 Correct 356 ms 22544 KB Output is correct
3 Correct 443 ms 22260 KB Output is correct
4 Correct 351 ms 22532 KB Output is correct
5 Correct 436 ms 22268 KB Output is correct
6 Correct 106 ms 20684 KB Output is correct
7 Correct 281 ms 19216 KB Output is correct
8 Correct 107 ms 20712 KB Output is correct
9 Correct 288 ms 19268 KB Output is correct
10 Correct 351 ms 19644 KB Output is correct
11 Correct 401 ms 19836 KB Output is correct
12 Correct 140 ms 20300 KB Output is correct
13 Correct 153 ms 20348 KB Output is correct
14 Correct 145 ms 22500 KB Output is correct
15 Correct 151 ms 22316 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Correct 899 ms 22620 KB Output is correct
18 Correct 713 ms 23624 KB Output is correct
19 Correct 894 ms 22804 KB Output is correct
20 Correct 912 ms 22696 KB Output is correct
21 Correct 850 ms 22656 KB Output is correct
22 Correct 738 ms 23536 KB Output is correct
23 Correct 828 ms 22384 KB Output is correct
24 Correct 952 ms 23124 KB Output is correct
25 Correct 864 ms 22900 KB Output is correct
26 Correct 948 ms 23004 KB Output is correct
27 Correct 254 ms 21252 KB Output is correct
28 Correct 250 ms 21188 KB Output is correct
29 Correct 255 ms 21216 KB Output is correct
30 Correct 770 ms 19588 KB Output is correct
31 Correct 762 ms 19444 KB Output is correct
32 Correct 1051 ms 20380 KB Output is correct
33 Correct 645 ms 20180 KB Output is correct
34 Correct 1067 ms 19700 KB Output is correct
35 Correct 775 ms 19188 KB Output is correct
36 Correct 876 ms 20472 KB Output is correct
37 Correct 329 ms 20680 KB Output is correct
38 Correct 299 ms 20556 KB Output is correct
39 Correct 362 ms 23240 KB Output is correct
40 Correct 333 ms 22944 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 356 ms 22544 KB Output is correct
3 Correct 443 ms 22260 KB Output is correct
4 Correct 351 ms 22532 KB Output is correct
5 Correct 436 ms 22268 KB Output is correct
6 Correct 106 ms 20684 KB Output is correct
7 Correct 281 ms 19216 KB Output is correct
8 Correct 107 ms 20712 KB Output is correct
9 Correct 288 ms 19268 KB Output is correct
10 Correct 351 ms 19644 KB Output is correct
11 Correct 401 ms 19836 KB Output is correct
12 Correct 140 ms 20300 KB Output is correct
13 Correct 153 ms 20348 KB Output is correct
14 Correct 145 ms 22500 KB Output is correct
15 Correct 151 ms 22316 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Incorrect 1961 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 12792 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Incorrect 12 ms 12924 KB Output isn't correct
6 Halted 0 ms 0 KB -