oj.uz

Submission #270683

# Submission time Handle Problem Language Result Execution time Memory
270683 2020-08-17T23:11:12 Z doowey Progression (NOI20_progression) C++14
44 / 100
 449 ms 138272 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;
            if(l + 1 <= r)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);
            if(l + 1 <= r)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 403 ms 69064 KB Output is correct
2 Correct 144 ms 636 KB Output is correct
3 Correct 148 ms 720 KB Output is correct
4 Correct 148 ms 632 KB Output is correct
5 Correct 145 ms 760 KB Output is correct
6 Correct 145 ms 760 KB Output is correct
7 Correct 153 ms 636 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 403 ms 69044 KB Output is correct
12 Correct 407 ms 68984 KB Output is correct
13 Correct 411 ms 69240 KB Output is correct
14 Correct 389 ms 69296 KB Output is correct
15 Correct 402 ms 69368 KB Output is correct
16 Correct 417 ms 68984 KB Output is correct
17 Correct 393 ms 69112 KB Output is correct
18 Correct 405 ms 68984 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 320 ms 69368 KB Output is correct
2 Correct 103 ms 1016 KB Output is correct
3 Correct 104 ms 1272 KB Output is correct
4 Correct 101 ms 992 KB Output is correct
5 Correct 105 ms 1016 KB Output is correct
6 Correct 103 ms 1016 KB Output is correct
7 Correct 103 ms 1016 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 416 KB Output is correct
11 Correct 374 ms 69240 KB Output is correct
12 Correct 324 ms 69508 KB Output is correct
13 Correct 369 ms 69368 KB Output is correct
14 Correct 377 ms 69240 KB Output is correct
15 Correct 333 ms 69368 KB Output is correct
16 Correct 376 ms 69752 KB Output is correct
17 Correct 385 ms 69752 KB Output is correct
18 Correct 449 ms 69880 KB Output is correct
19 Correct 405 ms 69064 KB Output is correct
20 Correct 362 ms 69112 KB Output is correct
21 Correct 405 ms 69112 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 138232 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 320 ms 69368 KB Output is correct
2 Correct 103 ms 1016 KB Output is correct
3 Correct 104 ms 1272 KB Output is correct
4 Correct 101 ms 992 KB Output is correct
5 Correct 105 ms 1016 KB Output is correct
6 Correct 103 ms 1016 KB Output is correct
7 Correct 103 ms 1016 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 416 KB Output is correct
11 Correct 374 ms 69240 KB Output is correct
12 Correct 324 ms 69508 KB Output is correct
13 Correct 369 ms 69368 KB Output is correct
14 Correct 377 ms 69240 KB Output is correct
15 Correct 333 ms 69368 KB Output is correct
16 Correct 376 ms 69752 KB Output is correct
17 Correct 385 ms 69752 KB Output is correct
18 Correct 449 ms 69880 KB Output is correct
19 Correct 405 ms 69064 KB Output is correct
20 Correct 362 ms 69112 KB Output is correct
21 Correct 405 ms 69112 KB Output is correct
22 Runtime error 161 ms 138272 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 403 ms 69064 KB Output is correct
2 Correct 144 ms 636 KB Output is correct
3 Correct 148 ms 720 KB Output is correct
4 Correct 148 ms 632 KB Output is correct
5 Correct 145 ms 760 KB Output is correct
6 Correct 145 ms 760 KB Output is correct
7 Correct 153 ms 636 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 403 ms 69044 KB Output is correct
12 Correct 407 ms 68984 KB Output is correct
13 Correct 411 ms 69240 KB Output is correct
14 Correct 389 ms 69296 KB Output is correct
15 Correct 402 ms 69368 KB Output is correct
16 Correct 417 ms 68984 KB Output is correct
17 Correct 393 ms 69112 KB Output is correct
18 Correct 405 ms 68984 KB Output is correct
19 Incorrect 2 ms 640 KB Output isn't correct
20 Halted 0 ms 0 KB -