Submission #908693

#	Time	Username	Problem	Language	Result	Execution time	Memory
908693		Tuanlinh123	Fish 2 (JOI22_fish2)	C++17	0 / 100	72 ms	53404 KiB

fish2

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

ll x[100005];

struct SegTree
{
    struct Node
    {
        ll ans=0, sum=0, len;
        vector <pair<ll, pll>> pre, suf;

        Node(){}
        Node(ll x)
        {
            ans=1, sum=x, len=1;
            pre.pb({0, {x, 0}});
            suf.pb({0, {x, 0}});
        }
    };

    Node Merge(Node a, Node b)
    {
        Node ans;
        ans.sum=a.sum+b.sum, ans.len=a.len+b.len;
        ans.pre=vector <pair<ll, pll>> (a.pre.begin(), a.pre.end());
        ans.suf=vector <pair<ll, pll>> (b.suf.begin(), b.suf.end());
        ll resa=a.ans, resb=b.ans, reqa=0, reqb=0;
        for (pair<ll, pll> p:a.suf)
            reqb=max(reqb, p.se.fi-p.fi);
        for (pair<ll, pll> p:b.pre)
            reqa=max(reqa, p.se.fi-p.fi);
        for (pair<ll, pll> p:b.pre)
            if (a.sum+p.fi<p.se.fi)
                ans.pre.pb({a.sum+p.fi, {p.se.fi, (p.fi>=reqb?p.se.se:0)+(resa?a.ans:0)}}), resa=0;
        for (pair<ll, pll> p:a.suf)
            if (p.fi+b.sum<p.se.fi)
                ans.suf.pb({p.fi+b.sum, {p.se.fi, (p.fi>=reqa?p.se.se:0)+(resb?b.ans:0)}}), resb=0;
        if (resa)
        {
            ll lo=0, ptra=0, ptrb=0;
            while (ptra<a.suf.size())
            {
                while (1)
                {
                    if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
                        ptra++;
                    else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
                        ptrb++;
                    else break;
                }    
                if (ptra==a.suf.size())
                {
                    if (ptrb==b.pre.size())
                        for (ll i=lo; i<ptra; i++)
                            resa+=a.suf[i].se.se;
                    break;
                }
                ptra++, lo=ptra;
            }
        }
        if (resb)
        {
            ll lo=0, ptra=0, ptrb=0;
            while (ptrb<b.pre.size())
            {
                while (1)
                {
                    if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
                        ptra++;
                    else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
                        ptrb++;
                    else break;
                }    
                if (ptrb==b.pre.size())
                {
                    if (ptra==a.suf.size())
                        for (ll i=lo; i<ptrb; i++)
                            resb+=b.pre[i].se.se;
                    break;
                }
                ptrb++, lo=ptrb;
            }
        }
        ans.ans=resa+resb;
        return ans;
    }

    void build(ll i, ll Start, ll End)
    {
        if (Start==End)
        {
            St[i]=Node(x[Start]);
            return;
        }
        ll mid=(Start+End)/2;
        build(i*2, Start, mid);
        build(i*2+1, mid+1, End);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }

    ll n;
    vector <Node> St;
    SegTree (ll n): n(n)
    {
        St.resize(n*4+1);
        build(1, 1, n);
    }

    void update(ll i, ll Start, ll End, ll idx, ll x)
    {
        if (Start>idx || End<idx)
            return;
        if (Start==End)
        {
            St[i]=Node(x);
            return;
        }
        ll mid=(Start+End)/2;
        update(i*2, Start, mid, idx, x);
        update(i*2+1, mid+1, End, idx, x);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }

    Node query(ll i, ll Start, ll End, ll l, ll r)
    {
        if (Start>=l && End<=r)
            return St[i];
        ll mid=(Start+End)/2;
        if (mid<l) return query(i*2+1, mid+1, End, l, r);
        if (mid+1>r) return query(i*2, Start, mid, l, r);
        return Merge(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
    }
};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<=n; i++)
        cin >> x[i];
    SegTree A(n);
    ll q; cin >> q;
    for (ll i=1; i<=q; i++)
    {
        ll t, a, b; cin >> t >> a >> b;
        if (t==1) A.update(1, 1, n, a, b);
        else cout << A.query(1, 1, n, a, b).ans << "\n";
    }
}

Compilation message (stderr)

fish2.cpp: In member function 'SegTree::Node SegTree::Merge(SegTree::Node, SegTree::Node)':
fish2.cpp:49:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while (ptra<a.suf.size())
      |                    ~~~~^~~~~~~~~~~~~
fish2.cpp:53:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
      |                         ~~~~^~~~~~~~~~~~~
fish2.cpp:53:66: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
      |                                                              ~~~~^~~~~~~~~~~~~~
fish2.cpp:55:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
      |                              ~~~~^~~~~~~~~~~~~
fish2.cpp:55:71: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
      |                                                                   ~~~~^~~~~~~~~~~~~~
fish2.cpp:59:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 if (ptra==a.suf.size())
      |                     ~~~~^~~~~~~~~~~~~~
fish2.cpp:61:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                     if (ptrb==b.pre.size())
      |                         ~~~~^~~~~~~~~~~~~~
fish2.cpp:72:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while (ptrb<b.pre.size())
      |                    ~~~~^~~~~~~~~~~~~
fish2.cpp:76:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                     if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
      |                         ~~~~^~~~~~~~~~~~~
fish2.cpp:76:66: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                     if (ptra<a.suf.size() && a.suf[ptra].fi+(ptrb==b.pre.size()?b.sum:b.pre[ptrb].fi)>=a.suf[ptra].se.fi)
      |                                                              ~~~~^~~~~~~~~~~~~~
fish2.cpp:78:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                     else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
      |                              ~~~~^~~~~~~~~~~~~
fish2.cpp:78:71: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                     else if (ptrb<b.pre.size() && b.pre[ptrb].fi+(ptra==a.suf.size()?a.sum:a.suf[ptra].fi)>=b.pre[ptrb].se.fi)
      |                                                                   ~~~~^~~~~~~~~~~~~~
fish2.cpp:82:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (ptrb==b.pre.size())
      |                     ~~~~^~~~~~~~~~~~~~
fish2.cpp:84:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                     if (ptra==a.suf.size())
      |                         ~~~~^~~~~~~~~~~~~~

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