oj.uz

Submission #1109395

# Submission time Handle Problem Language Result Execution time Memory
1109395 2024-11-06T15:46:16 Z ro9669 Progression (NOI20_progression) C++17
0 / 100
 845 ms 1048576 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(3e5)+7;

int n , q; ll a[maxN];

#define lef(id) id * 2
#define rig(id) id * 2 + 1

struct segtree_point{
    struct node{
        ll a , b , val;
        bool isAdd;

        node(){
            a = b = val = 0ll;
            isAdd = true;
        }

        void reset(){
            a = b = 0ll;
            isAdd = true;
        }
    } st[4 * maxN];

    void build(int id , int l , int r){
        if (l == r){
            st[id].val = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(lef(id) , l , mid);
        build(rig(id) , mid + 1 , r);
    }

    void modify(int id , ll a , ll b , bool isAdd){
        if (isAdd == false){
            st[id].a = a;
            st[id].b = b;
            st[id].isAdd = false;
        }
        else{
            st[id].a += a;
            st[id].b += b;
        }
    }

    void down(int id){
        ll a = st[id].a;
        ll b = st[id].b;
        bool isAdd = st[id].isAdd;
        modify(lef(id) , a , b , isAdd);
        modify(rig(id) , a , b , isAdd);
        st[id].reset();
    }

    void update(int id , int l , int r , int u , int v , ll a , ll b , bool isAdd){
        if (v < l || r < u) return;
        if (u <= l && r <= v){
            return modify(id , a , b , isAdd);
        }
        if (l != r) down(id);
        int mid = (l + r) / 2;
        update(lef(id) , l , mid , u , v , a , b , isAdd);
        update(rig(id) , mid + 1 , r , u , v , a , b , isAdd);
    }

    ll get(int id , int l , int r , int p){
        if (l == r){
            ll x = 1ll * st[id].a * p + st[id].b;
            if (st[id].isAdd == false){
                st[id].val = x;
            }
            else{
                st[id].val += x;
            }
            st[id].reset();
            return st[id].val;
        }
        if (l != r) down(id);
        int mid = (l + r) / 2;
        if (p <= mid){
            return get(lef(id) , l , mid , p);
        }
        else{
            return get(rig(id) , mid + 1 , r , p);
        }
    }
} A;

struct segtree_range{
    struct node{
        int val;
        ll st; int cnt_st;
        ll en; int cnt_en;
        bool same;
        ll lazy;
        bool isAdd;

        node(){
            val = 0;
            st = 0; cnt_st = 0;
            en = 0; cnt_en = 0;
            same = false;
            lazy = 0;
            isAdd = true;
        }
    } st[4 * maxN];

    node calc(node X , node Y){
        if (X.val == 0) return Y;
        if (Y.val == 0) return X;
        node ans;
        //
        ans.val = max(X.val , Y.val);
        if (X.en == Y.st){
            ans.val = max(ans.val , X.cnt_en + Y.cnt_st);
        }
        //
        ans.st = X.st;
        ans.cnt_st = X.cnt_st;
        if (X.same == true){
            if (X.en == Y.st) ans.cnt_st += Y.cnt_st;
        }
        //
        ans.en = Y.en;
        ans.cnt_en = Y.cnt_en;
        if (Y.same == true){
            if (X.en == Y.st) ans.cnt_en += X.cnt_en;
        }
        //
        if (X.same == true && Y.same == true && X.en == Y.st){
            ans.same = true;
        }
        else{
            ans.same = false;
        }
        //
        return ans;
    }

    void build(int id , int l , int r){
        if (l == r){
            st[id].val = 1;
            st[id].st = a[l + 1] - a[l]; st[id].cnt_st = 1;
            st[id].en = a[l + 1] - a[l]; st[id].cnt_en = 1;
            st[id].same = true;
            return;
        }
        int mid = (l + r) / 2;
        build(lef(id) , l , mid);
        build(rig(id) , mid + 1 , r);
        st[id] = calc(st[lef(id)] , st[rig(id)]);
    }

    void modify(int id , int l , int r , ll x , bool isAdd){
        if (isAdd == false){
            st[id].val = r - l + 1;
            st[id].st = x; st[id].cnt_st = r - l + 1;
            st[id].en = x; st[id].cnt_en = r - l + 1;
            st[id].same = true;
            st[id].lazy = x;
            st[id].isAdd = false;
        }
        else{
            st[id].st += x;
            st[id].en += x;
            st[id].lazy += x;
        }
    }

    void down(int id , int l , int r){
        ll &x = st[id].lazy;
        bool &isAdd = st[id].isAdd;
        int mid = (l + r) / 2;
        modify(lef(id) , l , mid , x , isAdd);
        modify(rig(id) , mid + 1 , r , x , isAdd);
        x = 0; isAdd = true;
    }

    void update(int id , int l , int r , int u , int v , ll x , bool isAdd){
        if (v < l || r < u) return;
        if (u <= l && r <= v){
            return modify(id , l , r , x , isAdd);
        }
        if (l != r) down(id , l , r);
        int mid = (l + r) / 2;
        update(lef(id) , l , mid , u , v , x , isAdd);
        update(rig(id) , mid + 1 , r , u , v , x , isAdd);
        st[id] = calc(st[lef(id)] , st[rig(id)]);
    }

    node get(int id , int l , int r , int u , int v){
        if (v < l || r < u) return node();
        if (u <= l && r <= v) return st[id];
        if (l != r) down(id , l , r);
        int mid = (l + r) / 2;
        return calc(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
    }
} B;

void solve(){
    cin >> n >> q;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    A.build(1 , 1 , n);
    B.build(1 , 1 , n - 1);
    for (int i = 1 ; i <= q ; i++){
        int t; cin >> t;
        if (t == 1){
            int l , r; ll s , c;
            cin >> l >> r >> s >> c;
            A.update(1 , 1 , n , l , r , 1ll * c , 1ll * s - 1ll * c * l, true);
            B.update(1 , 1 , n - 1 , l , r - 1 , 1ll * c , true);
            if (l - 1 >= 1){
                ll x = A.get(1 , 1 , n , l) - A.get(1 , 1 , n , l - 1);
                B.update(1 , 1 , n - 1 , l - 1 , l - 1 , x , false);
            }
            if (r + 1 <= n){
                ll x = A.get(1 , 1 , n , r + 1) - A.get(1 , 1 , n , r);
                B.update(1 , 1 , n - 1 , r , r , x , false);
            }
        }
        if (t == 2){
            int l , r; ll s , c;
            cin >> l >> r >> s >> c;
            A.update(1 , 1 , n , l , r , 1ll * c , 1ll * s - 1ll * c * l , false);
            B.update(1 , 1 , n - 1 , l , r - 1 , 1ll * c , false);
            if (l - 1 >= 1){
                ll x = A.get(1 , 1 , n , l) - A.get(1 , 1 , n , l - 1);
                B.update(1 , 1 , n - 1 , l - 1 , l - 1 , x , false);
            }
            if (r + 1 <= n){
                ll x = A.get(1 , 1 , n , r + 1) - A.get(1 , 1 , n , r);
                B.update(1 , 1 , n - 1 , r , r , x , false);
            }
        }
        if (t == 3){
            int l , r;
            cin >> l >> r;
            cout << B.get(1 , 1 , n - 1 , l , r - 1).val + 1 << "\n";
        }
    }
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:260:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:261:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  261 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 112700 KB Output is correct
2 Correct 71 ms 108440 KB Output is correct
3 Correct 72 ms 108484 KB Output is correct
4 Correct 71 ms 108360 KB Output is correct
5 Correct 78 ms 108468 KB Output is correct
6 Correct 72 ms 108360 KB Output is correct
7 Correct 75 ms 108360 KB Output is correct
8 Runtime error 828 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 105296 KB Output is correct
2 Correct 14 ms 105040 KB Output is correct
3 Correct 13 ms 105232 KB Output is correct
4 Correct 15 ms 105296 KB Output is correct
5 Runtime error 845 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 107644 KB Output is correct
2 Correct 79 ms 105692 KB Output is correct
3 Correct 76 ms 105800 KB Output is correct
4 Correct 75 ms 105800 KB Output is correct
5 Correct 77 ms 106996 KB Output is correct
6 Correct 82 ms 105800 KB Output is correct
7 Correct 78 ms 107080 KB Output is correct
8 Runtime error 827 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 111432 KB Output is correct
2 Correct 143 ms 105296 KB Output is correct
3 Correct 147 ms 107156 KB Output is correct
4 Correct 141 ms 105308 KB Output is correct
5 Correct 161 ms 105296 KB Output is correct
6 Correct 153 ms 107248 KB Output is correct
7 Correct 154 ms 106112 KB Output is correct
8 Runtime error 800 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 107644 KB Output is correct
2 Correct 79 ms 105692 KB Output is correct
3 Correct 76 ms 105800 KB Output is correct
4 Correct 75 ms 105800 KB Output is correct
5 Correct 77 ms 106996 KB Output is correct
6 Correct 82 ms 105800 KB Output is correct
7 Correct 78 ms 107080 KB Output is correct
8 Runtime error 827 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 112700 KB Output is correct
2 Correct 71 ms 108440 KB Output is correct
3 Correct 72 ms 108484 KB Output is correct
4 Correct 71 ms 108360 KB Output is correct
5 Correct 78 ms 108468 KB Output is correct
6 Correct 72 ms 108360 KB Output is correct
7 Correct 75 ms 108360 KB Output is correct
8 Runtime error 828 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -