oj.uz

Submission #270682

# Submission time Handle Problem Language Result Execution time Memory
270682 2020-08-17T23:03:13 Z doowey Progression (NOI20_progression) C++14
44 / 100
 404 ms 139768 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
const ll inf = (ll)1e18;
const ll F = -inf;

struct Node{
    ll sigma;
    ll set_l;
    ll add_l;
    int siz;
    ll lef_val;
    ll rig_val;
    int answer;
    int ans_pref;
    int ans_suff;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    if(T[node].set_l != (ll)1e18){
        T[node].sigma = T[node].siz * 1ll * T[node].set_l;
        T[node].lef_val = T[node].set_l;
        T[node].rig_val = T[node].set_l;
        T[node].answer = T[node].siz;
        T[node].ans_pref = T[node].siz;
        T[node].ans_suff = T[node].siz;
        T[node].add_l = 0ll;
        T[node * 2].set_l = T[node].set_l;
        T[node * 2 + 1].set_l = T[node].set_l;
        T[node].set_l = (ll)1e18;
    }
    else if(T[node].add_l != 0){
        T[node].sigma += T[node].siz * 1ll * T[node].add_l;
        T[node].lef_val += T[node].add_l;
        T[node].rig_val += T[node].add_l;
        T[node * 2].add_l += T[node].add_l;
        T[node * 2 + 1].add_l += T[node].add_l;
        T[node].add_l = 0ll;
    }
}

Node unite(Node A, Node B){
    Node ret;
    ret.sigma = A.sigma + B.sigma;
    ret.add_l = 0ll;
    ret.set_l = (ll)1e18;
    ret.siz = A.siz + B.siz;
    ret.answer = max(A.answer, B.answer);
    ret.lef_val = A.lef_val;
    ret.rig_val = B.rig_val;
    ret.ans_pref = A.ans_pref;
    ret.ans_suff = B.ans_suff;
    if(A.rig_val == B.lef_val){
        ret.answer = max(ret.answer, A.ans_suff + B.ans_pref);
        if(A.ans_pref == A.siz) ret.ans_pref += B.ans_pref;
        if(B.ans_suff == B.siz) ret.ans_suff += A.ans_suff;
    }
    return ret;
}

void upd1(int node, int cl, int cr, int tl, int tr, ll x){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].set_l = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd1(node * 2, cl, mid, tl, tr, x);
    upd1(node * 2 + 1, mid + 1, cr, tl, tr, x);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

void upd2(int node, int cl, int cr, int tl, int tr, ll x){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].add_l = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd2(node * 2, cl, mid, tl, tr, x);
    upd2(node * 2 + 1, mid + 1, cr, tl, tr, x);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

ll get_sum(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return 0ll;
    if(cl >= tl && cr <= tr){
        return T[node].sigma;
    }
    int mid = (cl + cr) / 2;
    return get_sum(node * 2, cl, mid, tl, tr) + get_sum(node * 2 + 1, mid + 1, cr, tl, tr);
}

Node cur;
bool has;

void query(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(tl > tr) return;
    if(cr < tl) return;
    if(cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(!has) {
            cur = T[node];
            has=true;
        }
        else{
            cur = unite(cur, T[node]);
        }
        return;
    }
    int mid = (cl + cr) / 2;
    query(node * 2, cl, mid, tl, tr);
    query(node * 2 + 1, mid + 1, cr, tl, tr);
}

int n;
ll A[N];

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node] = {A[cl], (ll)1e18, 0ll,cr-cl+1,A[cl],A[cl],1,1,1};
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

int main(){
    fastIO;
    int q;
    cin >> n >> q;
    A[0] = F;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
    }
    for(int i = n; i >= 1; i -- ){
        A[i] = A[i] - A[i - 1];
    }
    build(1, 0, n);
    int type;
    ll l, r, s, x;
    ll fb, fs;
    for(int i = 0 ; i < q; i ++ ){
        cin >> type;
        if(type == 1){
            cin >> l >> r >> s >> x;
            upd2(1, 0, n, l + 1, r, x);
            upd2(1, 0, n, l, l, s);
            if(r + 1 <= n)
                upd2(1, 0, n, r + 1, r + 1, -(s + (r - l) * 1ll * x));
        }
        else if(type == 2){
            cin >> l >> r >> s >> x;
            fb = get_sum(1, 0, n, 0, l - 1);
            if(r < n) fs = get_sum(1, 0, n, 0, r + 1);
            upd1(1, 0, n, l, l, s - fb);
            upd1(1, 0, n, l + 1, r, x);
            if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
        }
        else{
            cin >> l >> r;
            if(l == r){
                cout << 1 << "\n";
            }
            else{
                has=false;
                query(1, 0, n, l+1, r);
                cout << cur.answer + 1 << "\n";
            }
        }
    }
    return 0;
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:181:27: warning: 'fs' may be used uninitialized in this function [-Wmaybe-uninitialized]
  181 |             if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
      |                       ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 71196 KB Output is correct
2 Correct 145 ms 1272 KB Output is correct
3 Correct 144 ms 1404 KB Output is correct
4 Correct 141 ms 1400 KB Output is correct
5 Correct 141 ms 1400 KB Output is correct
6 Correct 145 ms 1400 KB Output is correct
7 Correct 141 ms 1360 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 386 ms 69852 KB Output is correct
12 Correct 389 ms 69624 KB Output is correct
13 Correct 388 ms 69880 KB Output is correct
14 Correct 389 ms 69880 KB Output is correct
15 Correct 381 ms 69880 KB Output is correct
16 Correct 403 ms 69624 KB Output is correct
17 Correct 394 ms 69624 KB Output is correct
18 Correct 404 ms 69624 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 70744 KB Output is correct
2 Correct 105 ms 2268 KB Output is correct
3 Correct 101 ms 2296 KB Output is correct
4 Correct 97 ms 2296 KB Output is correct
5 Correct 105 ms 2296 KB Output is correct
6 Correct 105 ms 2296 KB Output is correct
7 Correct 103 ms 2316 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 368 ms 70680 KB Output is correct
12 Correct 321 ms 71032 KB Output is correct
13 Correct 363 ms 70776 KB Output is correct
14 Correct 378 ms 70884 KB Output is correct
15 Correct 325 ms 70904 KB Output is correct
16 Correct 363 ms 71288 KB Output is correct
17 Correct 386 ms 71396 KB Output is correct
18 Correct 392 ms 71416 KB Output is correct
19 Correct 351 ms 70780 KB Output is correct
20 Correct 344 ms 70648 KB Output is correct
21 Correct 343 ms 70648 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 163 ms 139524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 70744 KB Output is correct
2 Correct 105 ms 2268 KB Output is correct
3 Correct 101 ms 2296 KB Output is correct
4 Correct 97 ms 2296 KB Output is correct
5 Correct 105 ms 2296 KB Output is correct
6 Correct 105 ms 2296 KB Output is correct
7 Correct 103 ms 2316 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 368 ms 70680 KB Output is correct
12 Correct 321 ms 71032 KB Output is correct
13 Correct 363 ms 70776 KB Output is correct
14 Correct 378 ms 70884 KB Output is correct
15 Correct 325 ms 70904 KB Output is correct
16 Correct 363 ms 71288 KB Output is correct
17 Correct 386 ms 71396 KB Output is correct
18 Correct 392 ms 71416 KB Output is correct
19 Correct 351 ms 70780 KB Output is correct
20 Correct 344 ms 70648 KB Output is correct
21 Correct 343 ms 70648 KB Output is correct
22 Runtime error 168 ms 139768 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 71196 KB Output is correct
2 Correct 145 ms 1272 KB Output is correct
3 Correct 144 ms 1404 KB Output is correct
4 Correct 141 ms 1400 KB Output is correct
5 Correct 141 ms 1400 KB Output is correct
6 Correct 145 ms 1400 KB Output is correct
7 Correct 141 ms 1360 KB Output is correct
8 Correct 2 ms 412 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 386 ms 69852 KB Output is correct
12 Correct 389 ms 69624 KB Output is correct
13 Correct 388 ms 69880 KB Output is correct
14 Correct 389 ms 69880 KB Output is correct
15 Correct 381 ms 69880 KB Output is correct
16 Correct 403 ms 69624 KB Output is correct
17 Correct 394 ms 69624 KB Output is correct
18 Correct 404 ms 69624 KB Output is correct
19 Incorrect 2 ms 640 KB Output isn't correct
20 Halted 0 ms 0 KB -