oj.uz

Submission #336643

# Submission time Handle Problem Language Result Execution time Memory
336643 2020-12-16T07:43:16 Z monkey8 Progression (NOI20_progression) C++14
35 / 100
 1126 ms 61932 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdio>
#include <utility> 
#include <queue>
#include <math.h>
#include <set>
#include <bitset>
#include <cmath>
#include <bitset>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 300010;
struct node {
    int maxleft, maxright, maxtot;
    ll kleft, kright, valleft, valright;
} st[MAXN << 2];
ll lazy[MAXN << 2];
int lazyClear[MAXN << 2];
int lazyS[MAXN << 2];
int lazyC[MAXN << 2];
ll val[MAXN];
int left(int p) {
    return (p << 1);
}
int right(int p) {
    return (p << 1) + 1;
}
node merge(node p1, int l1, int r1, node p2, int l2, int r2) {
    node newNode = node{p1.maxleft, p2.maxright, max(p1.maxtot, max(p2.maxtot, 2)), p1.kleft, p2.kright, p1.valleft, p2.valright};
    int num1 = r1 - l1 + 1;
    int num2 = r2 - l2 + 1;
    if(num1 == p1.maxleft) {
        if(p1.maxleft == 1 && p2.maxleft == 1) {
            newNode.maxleft = 2;
            newNode.kleft = p2.valleft - p1.valright;
        }
        else if(p1.maxleft == 1) {
            if(p2.valleft - p1.valright == p2.kleft) {
                newNode.maxleft = 1 + p2.maxleft;
                newNode.kleft = p2.kleft;
            }
            else {
                newNode.maxleft = 2;
                newNode.kleft = p2.valleft - p1.valright;
            }
        }
        else if(p2.maxleft == 1) {
            if(p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + 1;
                newNode.kleft = p1.kleft;
            }
        }
        else {
            if(p1.kleft == p2.kleft && p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + p2.maxleft;
                newNode.kleft = p1.kleft;
            }
            else if(p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + 1;
                newNode.kleft = p1.kleft;
            }
        }
    }
    if(num2 == p2.maxright) {
        if(p1.maxright == 1 && p2.maxright == 1) {
            newNode.maxright = 2;
            newNode.kright = p2.valleft - p1.valright;
        }
        else if(p1.maxright == 1) {
            if(p2.valleft - p1.valright == p2.kright) {
                newNode.maxright = 1 + p2.maxright;
                newNode.kright = p2.kright;
            }
        }
        else if(p2.maxright == 1) {
            if(p2.valleft - p1.valright == p1.kright) {
                newNode.maxright = p1.maxright + 1;
                newNode.kright = p1.kright;
            }
            else {
                newNode.maxright = 2;
                newNode.kright = p2.valleft - p1.valright;
            }
        }
        else {
            if(p1.kright == p2.kright && p2.valleft - p1.valright == p1.kright) {
                newNode.maxright = p1.maxright + p2.maxright;
                newNode.kright = p1.kright;
            }
            else if(p2.valleft - p1.valright == p2.kright) {
                newNode.maxright = 1 + p2.maxright;
                newNode.kright = p2.kright;
            }
        }
    }
    if(p1.maxright == 1 && p2.maxleft == 1) newNode.maxtot = max(newNode.maxtot, 2);
    else if(p1.maxright == 1) {
        if(p2.valleft - p1.valright == p2.kleft) newNode.maxtot = max(newNode.maxtot, 1 + p2.maxleft);
    }
    else if(p2.maxleft == 1) {
        if(p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + 1);
    }
    else {
        if(p1.kright == p2.kleft && p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + p2.maxleft);
        else if(p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + 1);
        else if(p2.valleft - p1.valright == p2.kleft) newNode.maxtot = max(newNode.maxtot, 1 + p2.maxleft);
    }
    return newNode;
}
void build(int p, int L, int R) {
    if(L == R) st[p] = node{1, 1, 1, 0, 0, val[L], val[R]};
    else {
        build(left(p), L, (L + R)/2);
        build(right(p), (L + R)/2 + 1, R);
        st[p] = merge(st[left(p)], L, (L + R)/2, st[right(p)], (L + R)/2 + 1, R);
    }
}
void push(int p, int L, int R) {
    st[p].valleft += lazyS[p] + lazyC[p] * (ll)L;
    st[p].valright += lazyS[p] + lazyC[p] * (ll)R;
    st[p].kleft += lazyC[p];
    st[p].kright += lazyC[p];
    if(L != R) {
        lazyS[left(p)] += lazyS[p];
        lazyC[left(p)] += lazyC[p];
        lazyS[right(p)] += lazyS[p];
        lazyC[right(p)] += lazyC[p];
    }
    lazyS[p] = 0;
    lazyC[p] = 0;
}
void update(int p, int L, int R, int i, int j, ll valS, ll valC) {
    push(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazyS[p] = valS;
        lazyC[p] = valC;
        push(p, L, R);
        return;
    }
    update(left(p), L, (L + R)/2, i, j, valS, valC);
    update(right(p), (L + R)/2 + 1, R, i, j, valS, valC);
    st[p] = merge(st[left(p)], L, (L + R)/2, st[right(p)], (L + R)/2 + 1, R);
}
node query(int p, int L, int R, int i, int j) {
    push(p, L, R);
    if(i > R || j < L) return node{-1, 0, 0, 0, 0, 0, 0};
    if(L >= i && R <= j) return st[p];
    node p1 = query(left(p), L, (L + R)/2, i, j);
    node p2 = query(right(p), (L + R)/2 + 1, R, i, j);
    if(p1.maxleft == -1) return p2; 
    if(p2.maxleft == -1) return p1;
    return merge(p1, L, (L + R)/2, p2, (L + R)/2 + 1, R);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++)
        cin >> val[i];
    build(1, 0, n - 1);
    for(int i = 0; i < q; i++) {
        int x; cin >> x;
        if(x == 3) {
            int l, r; cin >> l >> r;
            cout << query(1, 0, n - 1, l - 1, r - 1).maxtot << '\n';
        }
        else if(x == 1) {
            int l, r; ll s, c; cin >> l >> r >> s >> c;
            update(1, 0, n - 1, l - 1, r - 1, s - (ll)(l - 1) * c, c);
        }
    }
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 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 559 ms 61292 KB Output is correct
2 Correct 144 ms 1132 KB Output is correct
3 Correct 141 ms 1132 KB Output is correct
4 Correct 139 ms 1212 KB Output is correct
5 Correct 143 ms 1328 KB Output is correct
6 Correct 143 ms 1260 KB Output is correct
7 Correct 145 ms 1132 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 694 ms 61164 KB Output is correct
12 Correct 565 ms 61440 KB Output is correct
13 Correct 693 ms 61176 KB Output is correct
14 Correct 683 ms 61164 KB Output is correct
15 Correct 554 ms 61292 KB Output is correct
16 Correct 682 ms 61804 KB Output is correct
17 Correct 691 ms 61932 KB Output is correct
18 Correct 694 ms 61804 KB Output is correct
19 Correct 584 ms 60908 KB Output is correct
20 Correct 595 ms 60908 KB Output is correct
21 Correct 600 ms 61036 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 61292 KB Output is correct
2 Correct 144 ms 1132 KB Output is correct
3 Correct 141 ms 1132 KB Output is correct
4 Correct 139 ms 1212 KB Output is correct
5 Correct 143 ms 1328 KB Output is correct
6 Correct 143 ms 1260 KB Output is correct
7 Correct 145 ms 1132 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 694 ms 61164 KB Output is correct
12 Correct 565 ms 61440 KB Output is correct
13 Correct 693 ms 61176 KB Output is correct
14 Correct 683 ms 61164 KB Output is correct
15 Correct 554 ms 61292 KB Output is correct
16 Correct 682 ms 61804 KB Output is correct
17 Correct 691 ms 61932 KB Output is correct
18 Correct 694 ms 61804 KB Output is correct
19 Correct 584 ms 60908 KB Output is correct
20 Correct 595 ms 60908 KB Output is correct
21 Correct 600 ms 61036 KB Output is correct
22 Incorrect 1126 ms 60772 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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