oj.uz

Submission #1052826

# Submission time Handle Problem Language Result Execution time Memory
1052826 2024-08-11T03:03:07 Z Beerus13 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 205 ms 36688 KB 
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i)
#define REP(i, a, b)  for(int i = (a), _b = (b); i < _b;  ++i)
#define REPD(i, b, a) for(int i = (b), _a = (a); i > _a;  --i)
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define all(val) val.begin(), val.end()
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(v) (int)v.size()
#define fi first
#define se second

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);}

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);    
    }

const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 2e5 + 5;

struct node {
    ll a[2][2];
    node() { memset(a, 0, sizeof(a)); }
};

int n, q;
int a[N], d[N];
node st[N << 2];

node combine(node &l, node &r, int &pos) {
    node res;
    if(1ll * d[pos] * d[pos + 1] < 0) {
        REP(i, 0, 2) REP(j, 0, 2)
            res.a[i][j] = max(l.a[i][0] + r.a[1][j], l.a[i][1] + r.a[0][j]);
    } else {
        REP(i, 0, 2) REP(j, 0, 2) 
            res.a[i][j] = l.a[i][1] + r.a[1][j];
    }
    return res;
}

void update(int pos, int id = 1, int l = 1, int r = n) {
    if(l == r) {
        st[id].a[1][1] = abs(d[l]);
        return;
    }
    int m = l + r >> 1;
    if(pos <= m) update(pos, id << 1, l, m);
    else update(pos, id << 1 | 1, m + 1, r);
    st[id] = combine(st[id << 1], st[id << 1 | 1], m);
}

void process() {
    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> a[i];
        if(i > 1) {
            d[i] = a[i] - a[i - 1];
            update(i);
        }
    }
    while(q--) {
        int l, r, x; cin >> l >> r >> x;
        if(l > 1) {
            d[l] += x;
            update(l);
        }
        if(r < n) {
            d[r + 1] -= x;
            update(r + 1);
        }
        cout << st[1].a[1][1] << '\n';
    }
}

signed main() {
    if(fopen("test.inp","r")) {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // clock_t start = clock();

    int ntests = 1;
    // cin >> ntests;
    while(ntests--) process();

    // cerr << "Time elapsed: " << clock() - start << " ms!\n";
    return 0;
}
// https://oj.uz/problem/view/COCI21_sjeckanje

Compilation message

Main.cpp: In function 'void update(int, int, int, int)':
Main.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int m = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 3 ms 25436 KB Output is correct
3 Correct 2 ms 25436 KB Output is correct
4 Correct 3 ms 25436 KB Output is correct
5 Correct 3 ms 25476 KB Output is correct
6 Correct 3 ms 25436 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 3 ms 25436 KB Output is correct
3 Correct 2 ms 25436 KB Output is correct
4 Correct 3 ms 25436 KB Output is correct
5 Correct 3 ms 25476 KB Output is correct
6 Correct 3 ms 25436 KB Output is correct
7 Correct 5 ms 25432 KB Output is correct
8 Correct 5 ms 25436 KB Output is correct
9 Correct 5 ms 25632 KB Output is correct
10 Correct 5 ms 25644 KB Output is correct
11 Correct 6 ms 25432 KB Output is correct
12 Correct 5 ms 25436 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 3 ms 25436 KB Output is correct
3 Correct 2 ms 25436 KB Output is correct
4 Correct 3 ms 25436 KB Output is correct
5 Correct 3 ms 25476 KB Output is correct
6 Correct 3 ms 25436 KB Output is correct
7 Correct 5 ms 25432 KB Output is correct
8 Correct 5 ms 25436 KB Output is correct
9 Correct 5 ms 25632 KB Output is correct
10 Correct 5 ms 25644 KB Output is correct
11 Correct 6 ms 25432 KB Output is correct
12 Correct 5 ms 25436 KB Output is correct
13 Correct 191 ms 36432 KB Output is correct
14 Correct 205 ms 36136 KB Output is correct
15 Correct 194 ms 36176 KB Output is correct
16 Correct 203 ms 36040 KB Output is correct
17 Correct 191 ms 35924 KB Output is correct
18 Correct 191 ms 36688 KB Output is correct