Submission #736063

#	Time	Username	Problem	Language	Result	Execution time	Memory
736063		alireza_kaviani	Fish 2 (JOI22_fish2)	C++17	100 / 100	2686 ms	59184 KiB

fish2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 1e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

struct Data{
    ll dp, sum, nxt, cnt;

    Data(ll dp, ll sum, ll nxt, ll cnt){
        this->dp = dp;
        this->sum = sum;
        this->nxt = nxt;
        this->cnt = cnt;
    }
};

struct Node{
    bool empty;
    vector<Data> pref, suff;
    
    Node(){
        empty = true;
    }

    Node(int x, int prv, int nxt){
        empty = false;
        pref.push_back(Data(x, x, nxt, 1));
        suff.push_back(Data(x, x, prv, 1));
    }

    void Print(){
        return;
        cout << "Empty: " << empty << endl;
        for(Data i : pref){
            cout << i.dp << ' ' << i.cnt << ' ' << i.sum << ' ' << i.nxt << endl;
        }
        cout << "****" << endl;
        for(Data i : suff){
            cout << i.dp << ' ' << i.cnt << ' ' << i.sum << ' ' << i.nxt << endl;
        }
        cout << "=====" << endl;
    }
};

ll n, q, cnt = 0, A[MAXN];
Node seg[MAXN << 2];

ll calc(const vector<Data> &L, const vector<Data> &R, int n, int m){
    int ptr = 0, res = 0;
    for(int i = 0; i < n; i++){
        res += L[i].cnt;
        while(ptr < m && L[i].sum >= R[ptr].dp){
            ptr++;
        }
        if(i + 1 != n && (ptr == 0 || R[ptr - 1].sum + L[i].sum < L[i].nxt)){
            res = 0;
        }
    }
    return (ptr == m ? res : 0);
}

vector<Data> Merge(const vector<Data> &prefL, const vector<Data> &suffL, const vector<Data> &prefR){
    Data A = prefL.back();
    vector<Data> ans = prefL;
    int flag = 1;
    if(A.sum >= A.nxt){
        ans.pop_back();
        flag = 0;
    }
    ll cntR = 0;
    for(int i = 0; i < prefR.size(); i++){
        Data B = prefR[i];
        if(B.sum >= suffL.back().dp){
            cntR += B.cnt;
        }
        if(A.sum + B.sum >= B.nxt && i + 1 != SZ(prefR)){
            continue;
        }
        ll dp = max(A.dp, B.dp - A.sum);
        ll sum = min(INF, A.sum + B.sum);
        ll cnt = cntR;
        if(flag == 0){
            cnt = calc(suffL, prefR, SZ(suffL), i + 1);
            cnt += calc(prefR, suffL, i + 1, SZ(suffL));
        }
        ans.push_back(Data(dp, sum, B.nxt, cnt));
        cntR = 0;
        flag = 1;
    }
    return ans;
}

Node Merge(Node L, Node R){
    if(L.empty) return R;
    if(R.empty) return L;
    Node ans; ans.empty = false;
    ans.pref = Merge(L.pref, L.suff, R.pref);
    ans.suff = Merge(R.suff, R.pref, L.suff);
    L.Print();
    R.Print();
    ans.Print();
    return ans;
}

void build(int id = 1, int l = 1, int r = n + 1){
    if(r - l == 1){
        seg[id] = Node(A[l], A[l - 1], A[l + 1]);
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    seg[id] = Merge(seg[lc], seg[rc]);
}

void modify(int pos, int id = 1, int l = 1, int r = n + 1){
    if(r - l == 1){
        seg[id] = Node(A[l], A[l - 1], A[l + 1]);
        return;
    }
    int mid = l + r >> 1;
    if(pos < mid)   modify(pos, lc, l, mid);
    else    modify(pos, rc, mid, r);
    seg[id] = Merge(seg[lc], seg[rc]);
}

Node get(int ql, int qr, int id = 1, int l = 1, int r = n + 1){
    if(qr <= l || r <= ql)  return Node();
    if(ql <= l && r <= qr)  return seg[id];
    int mid = l + r >> 1;
    return Merge(get(ql, qr, lc, l, mid), get(ql, qr, rc, mid, r));
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    build();
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int x, y;
            cin >> x >> y;
            A[x] = y;
            if(x != 1)
                modify(x - 1);
            modify(x);
            if(x != n)
                modify(x + 1);
        }
        if(t == 2){
            int l, r;
            cin >> l >> r;
            r++;
            Node ans = get(l, r);
            cout << ans.pref.back().cnt << endl;
        }
    }

    return 0;
}
/*

*/

Compilation message (stderr)

fish2.cpp: In function 'std::vector<Data> Merge(const std::vector<Data>&, const std::vector<Data>&, const std::vector<Data>&)':
fish2.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < prefR.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
fish2.cpp: In function 'void build(int, int, int)':
fish2.cpp:126:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     int mid = l + r >> 1;
      |               ~~^~~
fish2.cpp: In function 'void modify(int, int, int, int)':
fish2.cpp:137:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |     int mid = l + r >> 1;
      |               ~~^~~
fish2.cpp: In function 'Node get(int, int, int, int, int)':
fish2.cpp:146:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17