/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 544.0 KiB
#3 Time Exceeded ≥2063ms ≥11.832 MiB
#4 Time Exceeded ≥2094ms ≥11.828 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define all(v) (v).begin(), (v).end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define F first 
#define S second

const ll M = 1e18 + 7;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

////////////////////////////////////   Segment Tree   ///////////////////////////////////////////////////////////////////////////////////////
class Node {
public: 
    int v = 0;

    Node(){}
    Node(int idn) {
        v = idn;
    }

    void merge(const Node& l, const Node& r) {
        v = l.v + r.v;
    }      
};

class Update{
public:
    int v = 0;

    Update(){}
    Update(int idn){
        v = idn;
    }
    
    void combine(const Update& newUpdate, const int& tl, const int& tr) {
        v = newUpdate.v;
    }
    
    void apply(Node& node, const int& tl, const int& tr) const {
        node.v = (tr - tl + 1) * v;
    }
};

template <typename node, typename update>
class SegTree {
public: 
    int len;
    vector<node> tree;
    vector<update> unpropUpd; 
    vector<bool> isLazy;
    node identityElement;
    update identityTransformation;


    SegTree(){}
    SegTree(int n) {
        len = n;
        tree.resize(4*len);
        isLazy.resize(4*len);
        unpropUpd.resize(4*len);
        identityElement = node();
        identityTransformation = update();
    }


    void apply(const int& v,const int& tl,const int& tr,const update& val) {
        if(tl != tr) {
            isLazy[v] = true;
            unpropUpd[v].combine(val,tl,tr);
        }
        val.apply(tree[v], tl, tr);
    }

    void pushdown(const int& v,const int& tl,const int& tr) {
        if(!isLazy[v]) return;
        isLazy[v] = false;

        int mid = (tl+tr)/2;
        apply(2*v, tl, mid, unpropUpd[v]);
        apply(2*v+1, mid+1, tr, unpropUpd[v]);
        unpropUpd[v] = identityTransformation;
    }

    template <typename T>
    void build(const T& a,const int& v,const int& tl,const int& tr) {
        if(tl == tr) {
            tree[v] = a[tl];
            return;
        }
        int mid = (tl+tr)/2;
        build(a, 2*v, tl, mid);    //left
        build(a, 2*v+1, mid+1,tr);  //right
        tree[v].merge(tree[2*v], tree[2*v+1]);
    }

    node query(const int& v,const int& tl,const int& tr,const int& l,const int& r) {

        if(r < tl || tr < l) return identityElement; 
        if(l <= tl && tr <= r) return tree[v]; 

        // partial overlap
        pushdown(v,tl,tr);
        int mid = (tl+tr)/2;
        node leftans = query(2*v, tl, mid, l, r);
        node rightans = query(2*v+1, mid+1, tr, l, r);
        node ans;
        ans.merge(leftans, rightans);

        return ans;
    }

    void rangeUpdate(const int& v,const int& tl,const int& tr,const int& l,const int& r, const update& val) {
        if(r < tl || tr < l) return;
        if(l <= tl && tr <= r) {
            apply(v,tl,tr,val);
            return;
        }

        // partial overlap
        pushdown(v,tl,tr);
        int mid = (tl+tr)/2;
        rangeUpdate(2*v, tl, mid, l, r, val);
        rangeUpdate(2*v+1, mid+1, tr, l, r, val);
        tree[v].merge(tree[2*v], tree[2*v+1]);
    }


   //over-ridden functions
   template<typename T>
   void build(const T& a) {
       build(a, 1, 0, len-1);
   }

   node query(const int& l,const int& r) {
       return query(1, 0, len-1, l, r);
   }

   void rangeUpdate(const int& l,const int& r, const update& val) {
       rangeUpdate(1, 0, len-1, l, r, val);
   }

};

// SegTree<Node, Update> tree(n);
// tree.build(a);

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Hrid_solve(){
    int n;
    cin >> n;

    vector<ll> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    int q;
    cin >> q;

    SegTree<Node, Update> tree(n);
    tree.build(v);

    while(q--) {
        int a,b,c;
        cin >> a >> b >> c;

        if(a==1) {
            tree.rangeUpdate(b-1,b-1,c);
        }
        else {
            vector<ll> tmp;
            for(int i = b-1; i < c; i++) {
                tmp.push_back(tree.query(i,i).v);
                // cout << tmp.back() << " ";
            }
            // cout << endl;

            if(is_sorted(all(tmp)) && (tmp.size()==1 || tmp[0] <= tmp.back())) yes;
            else no;
        }
    }
    
}


/* ************** What defines us is how well we rise after we Fall !! ************** */

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++){
        // cout << "Case " << kase << ": ";
        Hrid_solve();
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 18:18:34
Judged At
2024-11-11 03:10:42
Judged By
Score
20
Total Time
≥2094ms
Peak Memory
≥11.832 MiB