Submission #908347

#	Time	Username	Problem	Language	Result	Execution time	Memory
908347		Tuanlinh123	Fish 2 (JOI22_fish2)	C++17	0 / 100	89 ms	53564 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;
        for (pair<ll, pll> p:b.pre)
            if (a.sum+p.fi<p.se.fi)
                resa=0, ans.pre.pb({a.sum+p.fi, {p.se.fi, p.se.se+a.len}});
        for (pair<ll, pll> p:a.suf)
            if (p.fi+b.sum<p.se.fi)
                resb=0, ans.suf.pb({p.fi+b.sum, {p.se.fi, p.se.se+b.len}});
        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())
                        resa+=a.suf.back().se.se-(lo==0?0:a.suf[lo-1].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())
                        resb+=b.pre.back().se.se-(lo==0?0:b.pre[lo-1].se.se);
                    break;
                }
                ptrb++, lo=ptrb;
            }
        }
        ans.ans=resa+resb;
        // if (a.len!=0 && b.len!=0)
        // {
        //     cout << a.len << " " << b.len << " " << a.ans << " " << b.ans << " " << a.sum << " " << b.sum << "\n"; 
        //     for (pair<ll, pll> i:a.suf) cout << i.fi << " " << i.se.fi << " " << i.se.se << "\n";
        //     for (pair<ll, pll> i:b.pre) cout << i.fi << " " << i.se.fi << " " << i.se.se << "\n";
        //     cout << "ans " << resa << " " << resb << "\n";
        // }
        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:45: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]
   45 |             while (ptra<a.suf.size())
      |                    ~~~~^~~~~~~~~~~~~
fish2.cpp:49: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]
   49 |                     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:49: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]
   49 |                     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:51: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]
   51 |                     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:51: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]
   51 |                     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: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]
   55 |                 if (ptra==a.suf.size())
      |                     ~~~~^~~~~~~~~~~~~~
fish2.cpp:57: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]
   57 |                     if (ptrb==b.pre.size())
      |                         ~~~~^~~~~~~~~~~~~~
fish2.cpp:67: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]
   67 |             while (ptrb<b.pre.size())
      |                    ~~~~^~~~~~~~~~~~~
fish2.cpp:71: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]
   71 |                     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:71: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]
   71 |                     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:73: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]
   73 |                     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:73: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]
   73 |                     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:77: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]
   77 |                 if (ptrb==b.pre.size())
      |                     ~~~~^~~~~~~~~~~~~~
fish2.cpp:79: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]
   79 |                     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