oj.uz

Submission #1011641

# Submission time Handle Problem Language Result Execution time Memory
1011641 2024-07-01T02:25:10 Z Yang8on Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 7 ms 6492 KB 
#include <bits/stdc++.h>
#define Y8o "main"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
//#define f first
//#define s second

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);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, Q, cnt;
ll a[maxn], b[maxn], dp[maxn], dapan[maxn][2];
struct dl { int id, l, r; ll x; } qr[maxn];

void sub1()
{
    for(int i = 1; i <= n; i ++) b[i] = a[i];
    for(int _ = 1; _ <= Q; _ ++)
    {
        int id = qr[_].id, l = qr[_].l, r = qr[_].r; ll x = qr[_].x;
        if(id == 1)
            for(int j = l; j <= r; j ++) b[j] += x;
        else
        {
            for(int j = 1; j <= n; j ++) dp[j] = -1e18;
            dp[0] = 0;

            for(int j = 1; j <= n; j ++)
            {
                ll mx = -1e18, mi = 1e18;
                for(int t = j; t >= 1; t --)
                {
                    mx = max(mx, b[t]), mi = min(mi, b[t]);
                    dp[j] = max(dp[j], dp[t - 1] + mx - mi);
                }
            }
            cout << dp[n] << '\n';
//            dapan[++ cnt][0] = dp[n];
        }
    }
}

int fake(ll val, vector<ll> &v) {
    return lower_bound(v.begin(), v.end(), val) - v.begin() + 1;
}
ll bit1[maxn], bit2[maxn];
void update_up(int x, ll val) { while(x <= n) bit1[x] = max(bit1[x], val), x += (x & -x); }
ll get_dw(int x, ll best = -1e18) { while(x) best = max(best, bit1[x]), x -= (x & -x); return best; }
void update_dw(int x, ll val) { while(x) bit2[x] = max(bit2[x], val), x -= (x & -x); }
ll get_up(int x, ll best = -1e18) { while(x <= n) best = max(best, bit2[x]), x += (x & -x); return best; }

void sub2_1()
{
    vector<ll> v;
    for(int i = 1; i <= n; i ++) b[i] = a[i], v.push_back(b[i]);
    sort(v.begin(), v.end());


    for(int _ = 1; _ <= Q; _ ++)
    {
        int id = qr[_].id, l = qr[_].l, r = qr[_].r; ll x = qr[_].x;
        if(id == 1)
        {
            for(int j = l; j <= r; j ++) b[j] += x;
            v.clear();
            for(int j = 1; j <= n; j ++) v.push_back(b[j]);
            sort(v.begin(), v.end());
        }
        else
        {
            for(int j = 1; j <= n; j ++) bit1[j] = bit2[j] = -1e18;
            dp[0] = 0;
            update_dw(fake(b[1], v) - 1, dp[0] + b[1]);
            update_up(fake(b[1], v) + 1, dp[0] - b[1]);

            for(int j = 1; j <= n; j ++) {
                dp[j] = dp[j - 1];
                dp[j] = max(dp[j], get_up(fake(b[j], v)) - b[j] );
                dp[j] = max(dp[j], get_dw(fake(b[j], v)) + b[j] );

                update_up(fake(b[j + 1], v) + 1, dp[j] - b[j + 1]);
                update_dw(fake(b[j + 1], v) - 1, dp[j] + b[j + 1]);

//                for(int t = j; t >= 1; t --) {
//                    dp[j] = max(dp[j], dp[t - 1] + abs(b[j] - b[t]));
//                }
            }

            cout << dp[n] << '\n';
//            dapan[++ cnt][1] = dp[n];
        }
    }
}

void Inp()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= Q; i ++)
    {
        int id, l = 0, r = 0; ll x = 0;
        cin >> id;
        if(id == 1) cin >> l >> r >> x;
        qr[i] = {id, l, r, x};
    }
}
void Sinh()
{
    n = GetRandom(20, 20), Q = GetRandom(20, 20);
    cout << n << ' ' << Q << '\n';
    for(int i = 1; i <= n ; i++)
    {
        a[i] = GetRandom(-1e8, 1e8);
        cout << a[i] << ' ';
    }
    cout << '\n';
    for(int i = 1; i <= Q; i ++)
    {
        int id = GetRandom(1, 2), l = GetRandom(1, n), r = GetRandom(1, n), x = GetRandom(-1e8, 1e8);
        cout << id << ' ';
        if(id == 1) cout << l << ' ' <<r << ' ' << x << '\n';
        else cout << '\n';
        qr[i] = {id, l, r, x};
    }
}

void solve()
{
    Inp();
//    Sinh();
//    sub1(), cnt = 0;
//    sub2_1();
//    cout << "ANS :" << '\n';
//    for(int i = 1; i <= cnt; i ++) cout << dapan[i][0] << ' ' << dapan[i][1] << '\n';

    if(max(n, Q) <= 200) sub1();
    else if(max(n, Q) <= 3000) sub2_1();
}


int main()
{
    iof();

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

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

    ctime();
    return 0;
}

Compilation message

Main.cpp: In function 'void iof()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 55.0

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