oj.uz

답안 #893808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893808 2023-12-27T13:18:34 Z yfrank792 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 487 ms 36436 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef set<int> si;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<int,vi,greater<int> > pqi_g;
typedef priority_queue<ll,vll,greater<ll> > pql_g;

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define _FOR(i,a,b) for (int i=a; i>=b; i--)
#define F0R(i,a,b,x) for (int i=a; i<=b; i+=x)
#define FOR_(x,v) for (auto x : v)
#define F0R_(x,v) for (auto &x : v)

const int INF = 0x3f3f3f3f;
const int maxn = 2e5+2;
const ll MOD = 1e9+7;

//? link: https://oj.uz/problem/view/COCI21_sjeckanje

//? sol: segtree
//          - it can be observed that the segments that will produce the max total value are always either increasing or decreasing
//          - since the max total value is sum of the difference b/t the max and min values in each segment, we can store the array as one of differences
//          - this way, the value for a segment is just the sum of the differences in that segment
//          - when making updates, we then only need to change the end values of the segments that are affected
//          - we can then use a segtree to store the difference array
//          - since each segment must be one spaced apart (can't use the same element twice), we store the max value for each segtree node given 4 scenarios:
//              - take the left value and the right value
//              - take the left value and not the right value
//              - take the right value and not the left value
//              - take neither the left value nor the right value
//          - we also store the left and right border values for each node

int n, q;
class segtree {
    struct node {ll yy,yn,ny,nn,l,r;} d[4*maxn];
    private:
        ll inline ls(ll x) {return x<<1;}
        ll inline rs(ll x) {return x<<1|1;}
        node inline op(node &l,node &r) {
            node ret = {
                max(l.yn+r.yy, l.yy+r.ny),          // yy
                max(l.yy+r.nn, l.yn+r.yn),          // yn
                max(l.ny+r.ny, l.nn+r.yy),          // ny
                max(l.ny+r.nn, l.nn+r.yn),          // nn
                l.l,                                // l
                r.r                                 // r
            };
            if ((l.r>=0 && r.l>=0) || (l.r<=0 && r.l<=0)) {
                ret.yy = max(ret.yy, l.yy+r.yy);
                ret.yn = max(ret.yn, l.yy+r.yn);
                ret.ny = max(ret.ny, l.ny+r.yy);
                ret.nn = max(ret.nn, l.ny+r.yn);
            }
            return ret;
        }
    public:
        ll a[maxn];
        void init(ll s=1,ll t=n,ll p=1) {
            if (s==t) {
                d[p] = {abs(a[s]),0,0,0,a[s],a[s]};
                return;
            }
            ll mid = s + ((t-s)>>1);
            init(s, mid, ls(p));
            init(mid+1, t, rs(p));
            d[p] = op(d[ls(p)], d[rs(p)]);
        }
        void upd(ll v,ll x,ll s=1,ll t=n,ll p=1) {      // upd pos v by value x ~ p=cur pos, s,t=cur range
            if (s==t) {
                a[s] += x;
                d[p] = {abs(a[s]),0,0,0,a[s],a[s]};
                return;
            }
            ll mid = s + ((t-s)>>1);
            if (v<=mid) upd(v,x,s,mid,ls(p));
            else upd(v,x,mid+1,t,rs(p));
            d[p] = op(d[ls(p)], d[rs(p)]);
        }
        ll query() {
            return max(d[1].yy, max(d[1].yn, max(d[1].ny, d[1].nn)));
        }
        void output_a() {
            FOR(i,1,n) cout << a[i] << " ";
            cout << endl;
        }
} st;

int main()
{
    // faster cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("c.in","r",stdin);

    cin >> n >> q;
    int last; cin>>last; st.a[1]=0;
    FOR(i,2,n) {
        int x; cin>>x;
        st.a[i] = x-last;
        last = x;
    }
    st.init();

    FOR(_,1,q) {
        int l,r,x; cin>>l>>r>>x;
        if (l!=1) st.upd(l,x);
        if (r!=n) st.upd(r+1,-x);
        // st.output_a();
        cout << st.query() << endl;
    }

    return 0;   
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 6 ms 2652 KB Output is correct
9 Correct 7 ms 2652 KB Output is correct
10 Correct 6 ms 2652 KB Output is correct
11 Correct 7 ms 2624 KB Output is correct
12 Correct 6 ms 2648 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 6 ms 2652 KB Output is correct
9 Correct 7 ms 2652 KB Output is correct
10 Correct 6 ms 2652 KB Output is correct
11 Correct 7 ms 2624 KB Output is correct
12 Correct 6 ms 2648 KB Output is correct
13 Correct 487 ms 35888 KB Output is correct
14 Correct 467 ms 35864 KB Output is correct
15 Correct 462 ms 35920 KB Output is correct
16 Correct 475 ms 35700 KB Output is correct
17 Correct 463 ms 35668 KB Output is correct
18 Correct 437 ms 36436 KB Output is correct