oj.uz

Submission #1109404

# Submission time Handle Problem Language Result Execution time Memory
1109404 2024-11-06T15:58:17 Z ro9669 Progression (NOI20_progression) C++17
100 / 100
 984 ms 107148 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;
        bool isAdd;

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

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

    void build(int id , int l , int r){
        if (l == r) 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){
                a[l] = x;
            }
            else{
                a[l] += x;
            }
            st[id].reset();
            return a[l];
        }
        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);
    if (n > 1) 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:257:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  257 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:258:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 97352 KB Output is correct
2 Correct 69 ms 95304 KB Output is correct
3 Correct 69 ms 95304 KB Output is correct
4 Correct 67 ms 95324 KB Output is correct
5 Correct 89 ms 95304 KB Output is correct
6 Correct 70 ms 95304 KB Output is correct
7 Correct 68 ms 95304 KB Output is correct
8 Correct 15 ms 94800 KB Output is correct
9 Correct 14 ms 94800 KB Output is correct
10 Correct 16 ms 94800 KB Output is correct
11 Correct 142 ms 105292 KB Output is correct
12 Correct 150 ms 105288 KB Output is correct
13 Correct 182 ms 105376 KB Output is correct
14 Correct 145 ms 105720 KB Output is correct
15 Correct 196 ms 105524 KB Output is correct
16 Correct 114 ms 105300 KB Output is correct
17 Correct 125 ms 105288 KB Output is correct
18 Correct 130 ms 105288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 94800 KB Output is correct
2 Correct 14 ms 94800 KB Output is correct
3 Correct 17 ms 94800 KB Output is correct
4 Correct 17 ms 94800 KB Output is correct
5 Correct 13 ms 94800 KB Output is correct
6 Correct 13 ms 94800 KB Output is correct
7 Correct 15 ms 94800 KB Output is correct
8 Correct 17 ms 94800 KB Output is correct
9 Correct 19 ms 94800 KB Output is correct
10 Correct 15 ms 95036 KB Output is correct
11 Correct 15 ms 94800 KB Output is correct
12 Correct 15 ms 95040 KB Output is correct
13 Correct 17 ms 94800 KB Output is correct
14 Correct 15 ms 95048 KB Output is correct
15 Correct 15 ms 95036 KB Output is correct
16 Correct 16 ms 94924 KB Output is correct
17 Correct 15 ms 95056 KB Output is correct
18 Correct 17 ms 95056 KB Output is correct
19 Correct 13 ms 94968 KB Output is correct
20 Correct 17 ms 94800 KB Output is correct
21 Correct 15 ms 94800 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 97612 KB Output is correct
2 Correct 88 ms 95560 KB Output is correct
3 Correct 86 ms 95572 KB Output is correct
4 Correct 66 ms 95572 KB Output is correct
5 Correct 71 ms 95560 KB Output is correct
6 Correct 94 ms 95560 KB Output is correct
7 Correct 83 ms 95536 KB Output is correct
8 Correct 12 ms 94800 KB Output is correct
9 Correct 13 ms 94800 KB Output is correct
10 Correct 12 ms 94800 KB Output is correct
11 Correct 239 ms 102228 KB Output is correct
12 Correct 236 ms 103728 KB Output is correct
13 Correct 232 ms 102216 KB Output is correct
14 Correct 290 ms 102360 KB Output is correct
15 Correct 261 ms 103752 KB Output is correct
16 Correct 275 ms 104364 KB Output is correct
17 Correct 291 ms 104216 KB Output is correct
18 Correct 237 ms 104444 KB Output is correct
19 Correct 207 ms 103744 KB Output is correct
20 Correct 242 ms 103752 KB Output is correct
21 Correct 272 ms 103756 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 96840 KB Output is correct
2 Correct 184 ms 95048 KB Output is correct
3 Correct 182 ms 95044 KB Output is correct
4 Correct 145 ms 95052 KB Output is correct
5 Correct 156 ms 95104 KB Output is correct
6 Correct 154 ms 95044 KB Output is correct
7 Correct 152 ms 95048 KB Output is correct
8 Correct 12 ms 94800 KB Output is correct
9 Correct 12 ms 94800 KB Output is correct
10 Correct 13 ms 94812 KB Output is correct
11 Correct 767 ms 103112 KB Output is correct
12 Correct 754 ms 106388 KB Output is correct
13 Correct 678 ms 103240 KB Output is correct
14 Correct 777 ms 103240 KB Output is correct
15 Correct 822 ms 106436 KB Output is correct
16 Correct 729 ms 106644 KB Output is correct
17 Correct 772 ms 106520 KB Output is correct
18 Correct 797 ms 106568 KB Output is correct
19 Correct 853 ms 106568 KB Output is correct
20 Correct 798 ms 106568 KB Output is correct
21 Correct 732 ms 106556 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 97612 KB Output is correct
2 Correct 88 ms 95560 KB Output is correct
3 Correct 86 ms 95572 KB Output is correct
4 Correct 66 ms 95572 KB Output is correct
5 Correct 71 ms 95560 KB Output is correct
6 Correct 94 ms 95560 KB Output is correct
7 Correct 83 ms 95536 KB Output is correct
8 Correct 12 ms 94800 KB Output is correct
9 Correct 13 ms 94800 KB Output is correct
10 Correct 12 ms 94800 KB Output is correct
11 Correct 239 ms 102228 KB Output is correct
12 Correct 236 ms 103728 KB Output is correct
13 Correct 232 ms 102216 KB Output is correct
14 Correct 290 ms 102360 KB Output is correct
15 Correct 261 ms 103752 KB Output is correct
16 Correct 275 ms 104364 KB Output is correct
17 Correct 291 ms 104216 KB Output is correct
18 Correct 237 ms 104444 KB Output is correct
19 Correct 207 ms 103744 KB Output is correct
20 Correct 242 ms 103752 KB Output is correct
21 Correct 272 ms 103756 KB Output is correct
22 Correct 804 ms 105816 KB Output is correct
23 Correct 158 ms 98120 KB Output is correct
24 Correct 157 ms 98104 KB Output is correct
25 Correct 140 ms 98120 KB Output is correct
26 Correct 139 ms 98128 KB Output is correct
27 Correct 148 ms 98120 KB Output is correct
28 Correct 134 ms 98176 KB Output is correct
29 Correct 14 ms 94800 KB Output is correct
30 Correct 14 ms 94800 KB Output is correct
31 Correct 13 ms 95056 KB Output is correct
32 Correct 770 ms 103180 KB Output is correct
33 Correct 827 ms 106024 KB Output is correct
34 Correct 832 ms 103244 KB Output is correct
35 Correct 785 ms 103112 KB Output is correct
36 Correct 564 ms 102948 KB Output is correct
37 Correct 590 ms 102984 KB Output is correct
38 Correct 592 ms 103060 KB Output is correct
39 Correct 757 ms 106056 KB Output is correct
40 Correct 754 ms 106056 KB Output is correct
41 Correct 796 ms 106056 KB Output is correct
42 Correct 811 ms 106056 KB Output is correct
43 Correct 716 ms 105832 KB Output is correct
44 Correct 740 ms 105952 KB Output is correct
45 Correct 775 ms 106056 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 97352 KB Output is correct
2 Correct 69 ms 95304 KB Output is correct
3 Correct 69 ms 95304 KB Output is correct
4 Correct 67 ms 95324 KB Output is correct
5 Correct 89 ms 95304 KB Output is correct
6 Correct 70 ms 95304 KB Output is correct
7 Correct 68 ms 95304 KB Output is correct
8 Correct 15 ms 94800 KB Output is correct
9 Correct 14 ms 94800 KB Output is correct
10 Correct 16 ms 94800 KB Output is correct
11 Correct 142 ms 105292 KB Output is correct
12 Correct 150 ms 105288 KB Output is correct
13 Correct 182 ms 105376 KB Output is correct
14 Correct 145 ms 105720 KB Output is correct
15 Correct 196 ms 105524 KB Output is correct
16 Correct 114 ms 105300 KB Output is correct
17 Correct 125 ms 105288 KB Output is correct
18 Correct 130 ms 105288 KB Output is correct
19 Correct 14 ms 94800 KB Output is correct
20 Correct 14 ms 94800 KB Output is correct
21 Correct 17 ms 94800 KB Output is correct
22 Correct 17 ms 94800 KB Output is correct
23 Correct 13 ms 94800 KB Output is correct
24 Correct 13 ms 94800 KB Output is correct
25 Correct 15 ms 94800 KB Output is correct
26 Correct 17 ms 94800 KB Output is correct
27 Correct 19 ms 94800 KB Output is correct
28 Correct 15 ms 95036 KB Output is correct
29 Correct 15 ms 94800 KB Output is correct
30 Correct 15 ms 95040 KB Output is correct
31 Correct 17 ms 94800 KB Output is correct
32 Correct 15 ms 95048 KB Output is correct
33 Correct 15 ms 95036 KB Output is correct
34 Correct 16 ms 94924 KB Output is correct
35 Correct 15 ms 95056 KB Output is correct
36 Correct 17 ms 95056 KB Output is correct
37 Correct 13 ms 94968 KB Output is correct
38 Correct 17 ms 94800 KB Output is correct
39 Correct 15 ms 94800 KB Output is correct
40 Correct 232 ms 97612 KB Output is correct
41 Correct 88 ms 95560 KB Output is correct
42 Correct 86 ms 95572 KB Output is correct
43 Correct 66 ms 95572 KB Output is correct
44 Correct 71 ms 95560 KB Output is correct
45 Correct 94 ms 95560 KB Output is correct
46 Correct 83 ms 95536 KB Output is correct
47 Correct 12 ms 94800 KB Output is correct
48 Correct 13 ms 94800 KB Output is correct
49 Correct 12 ms 94800 KB Output is correct
50 Correct 239 ms 102228 KB Output is correct
51 Correct 236 ms 103728 KB Output is correct
52 Correct 232 ms 102216 KB Output is correct
53 Correct 290 ms 102360 KB Output is correct
54 Correct 261 ms 103752 KB Output is correct
55 Correct 275 ms 104364 KB Output is correct
56 Correct 291 ms 104216 KB Output is correct
57 Correct 237 ms 104444 KB Output is correct
58 Correct 207 ms 103744 KB Output is correct
59 Correct 242 ms 103752 KB Output is correct
60 Correct 272 ms 103756 KB Output is correct
61 Correct 804 ms 96840 KB Output is correct
62 Correct 184 ms 95048 KB Output is correct
63 Correct 182 ms 95044 KB Output is correct
64 Correct 145 ms 95052 KB Output is correct
65 Correct 156 ms 95104 KB Output is correct
66 Correct 154 ms 95044 KB Output is correct
67 Correct 152 ms 95048 KB Output is correct
68 Correct 12 ms 94800 KB Output is correct
69 Correct 12 ms 94800 KB Output is correct
70 Correct 13 ms 94812 KB Output is correct
71 Correct 767 ms 103112 KB Output is correct
72 Correct 754 ms 106388 KB Output is correct
73 Correct 678 ms 103240 KB Output is correct
74 Correct 777 ms 103240 KB Output is correct
75 Correct 822 ms 106436 KB Output is correct
76 Correct 729 ms 106644 KB Output is correct
77 Correct 772 ms 106520 KB Output is correct
78 Correct 797 ms 106568 KB Output is correct
79 Correct 853 ms 106568 KB Output is correct
80 Correct 798 ms 106568 KB Output is correct
81 Correct 732 ms 106556 KB Output is correct
82 Correct 804 ms 105816 KB Output is correct
83 Correct 158 ms 98120 KB Output is correct
84 Correct 157 ms 98104 KB Output is correct
85 Correct 140 ms 98120 KB Output is correct
86 Correct 139 ms 98128 KB Output is correct
87 Correct 148 ms 98120 KB Output is correct
88 Correct 134 ms 98176 KB Output is correct
89 Correct 14 ms 94800 KB Output is correct
90 Correct 14 ms 94800 KB Output is correct
91 Correct 13 ms 95056 KB Output is correct
92 Correct 770 ms 103180 KB Output is correct
93 Correct 827 ms 106024 KB Output is correct
94 Correct 832 ms 103244 KB Output is correct
95 Correct 785 ms 103112 KB Output is correct
96 Correct 564 ms 102948 KB Output is correct
97 Correct 590 ms 102984 KB Output is correct
98 Correct 592 ms 103060 KB Output is correct
99 Correct 757 ms 106056 KB Output is correct
100 Correct 754 ms 106056 KB Output is correct
101 Correct 796 ms 106056 KB Output is correct
102 Correct 811 ms 106056 KB Output is correct
103 Correct 716 ms 105832 KB Output is correct
104 Correct 740 ms 105952 KB Output is correct
105 Correct 775 ms 106056 KB Output is correct
106 Correct 955 ms 106824 KB Output is correct
107 Correct 189 ms 98376 KB Output is correct
108 Correct 180 ms 98376 KB Output is correct
109 Correct 181 ms 98268 KB Output is correct
110 Correct 15 ms 94928 KB Output is correct
111 Correct 12 ms 94916 KB Output is correct
112 Correct 13 ms 94800 KB Output is correct
113 Correct 713 ms 106032 KB Output is correct
114 Correct 842 ms 106120 KB Output is correct
115 Correct 785 ms 105836 KB Output is correct
116 Correct 748 ms 105884 KB Output is correct
117 Correct 910 ms 106824 KB Output is correct
118 Correct 784 ms 105796 KB Output is correct
119 Correct 791 ms 105820 KB Output is correct
120 Correct 225 ms 104520 KB Output is correct
121 Correct 227 ms 104524 KB Output is correct
122 Correct 253 ms 104520 KB Output is correct
123 Correct 224 ms 103752 KB Output is correct
124 Correct 219 ms 103752 KB Output is correct
125 Correct 230 ms 103752 KB Output is correct
126 Correct 920 ms 103496 KB Output is correct
127 Correct 925 ms 103616 KB Output is correct
128 Correct 978 ms 107148 KB Output is correct
129 Correct 848 ms 103496 KB Output is correct
130 Correct 544 ms 103496 KB Output is correct
131 Correct 578 ms 103496 KB Output is correct
132 Correct 565 ms 103632 KB Output is correct
133 Correct 890 ms 107072 KB Output is correct
134 Correct 887 ms 106992 KB Output is correct
135 Correct 984 ms 106840 KB Output is correct
136 Correct 175 ms 98256 KB Output is correct
137 Correct 176 ms 98336 KB Output is correct
138 Correct 173 ms 98376 KB Output is correct