oj.uz

답안 #883636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883636 2023-12-05T14:48:55 Z Yang8on Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 272 ms 31680 KB 
#include <bits/stdc++.h>

#define Yang8on Nguyen_Dinh_Son
#define sonphamay Nguyen_Dinh_Son

#define aothtday "Sjeckanje"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define endl '\n'
#define pii pair<int, ll>
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define maxn 200005
#define maxm
#define maxx
#define mod 1000000007
#define base 311
#define ModHas 1000000003ll
#define gb(i, j) ((i >> j) & 1)
#define int long long

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q;
ll a[maxn], d[maxn], dp[maxn];
struct dl
{
    ll op_op, op_cl, cl_op, cl_cl;

    void cb(dl x, dl y, int mid)
    {
        op_op = max(x.op_op + y.cl_op, x.op_cl + y.op_op);
        op_cl = max(x.op_op + y.cl_cl, x.op_cl + y.op_cl);
        cl_op = max(x.cl_op + y.cl_op, x.cl_cl + y.op_op);
        cl_cl = max(x.cl_op + y.cl_cl, x.cl_cl + y.op_cl);

        if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
        {
            op_op = max(x.op_op, x.op_cl) + max(y.op_op, y.cl_op);
            op_cl = max(x.op_op, x.op_cl) + max(y.op_cl, y.cl_cl);
            cl_op = max(x.cl_op, x.cl_cl) + max(y.cl_op, y.op_op);
            cl_cl = max(x.cl_op, x.cl_cl) + max(y.op_cl, y.cl_cl);
        }
    }

} st[4 * maxn];

void built(int id = 1, int l = 1, int r = n - 1)
{
    if(l == r)
    {
        st[id].op_op = abs(d[l]);
        return ;
    }

    int mid = (l + r) >> 1;

    built(id * 2, l, mid);
    built(id * 2 + 1, mid + 1, r);

    st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}

void update(int pos, int id = 1, int l = 1, int r = n - 1)
{
    if(pos < l || r < pos) return ;
    if(l == r)
    {
        st[id].op_op = abs(d[pos]), st[id].op_cl = st[id].cl_op = st[id].cl_cl = 0;
        return ;
    }

    int mid = (l + r) >> 1;

    update(pos, id * 2, l, mid);
    update(pos, id * 2 + 1, mid + 1, r);

    st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}

void solve()
{
    cin >> n >> q;
    fi(i, 1, n) cin >> a[i];
    fi(i, 1, n - 1) d[i] = a[i] - a[i + 1];
//    n = GetRandom(20, 20), q = GetRandom(10, 10);
//    cout << n << ' ' << q << '\n';
//    fi(i, 1, n) a[i] = GetRandom(1, 10), cout << a[i] << ' ' ;
//    cout << '\n';
//    fi(i, 1, n - 1) d[i] = a[i] - a[i + 1];

    built();

    fi(_, 1, q)
    {
        int l, r;
        ll x;
        cin >> l >> r >> x;
//        l = GetRandom(1, n), r = GetRandom(1, n), x = GetRandom(1, 10);
//        if(l > r) swap(l, r);
//        cout << l << ' ' << r << ' ' << x << ' ' << "ANS" << ' ';

        if(l - 1 != 0)
        {
            d[l - 1] -= x;
            update(l - 1);
        }

        d[r] += x;
        update(r);

        cout << max({st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl})  << '\n';
//        fi(i, l, r) a[i] += x;
//        fi(i, 1, n) fi(j, 1, i) dp[i] = max(dp[i], abs(a[i] - a[j]) + dp[j - 1]);
//
//        cout << dp[n] << ' ' << max({st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl}) << '\n';
//
//        fi(i, 1, n) dp[i] = 0;
    }
}

signed main()
{
    if(fopen(aothtday".inp", "r"))
    {
        freopen(aothtday".inp","r",stdin);
        freopen(aothtday".out","w",stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In member function 'void dl::cb(dl, dl, long long int)':
Main.cpp:48:56: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   48 |         if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
      |                                                 ~~~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(aothtday".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(aothtday".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4568 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 6880 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 4 ms 6744 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6744 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4568 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 6880 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 4 ms 6744 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6744 KB Output is correct
13 Correct 244 ms 30968 KB Output is correct
14 Correct 246 ms 31056 KB Output is correct
15 Correct 272 ms 31020 KB Output is correct
16 Correct 261 ms 31200 KB Output is correct
17 Correct 250 ms 30800 KB Output is correct
18 Correct 230 ms 31680 KB Output is correct