oj.uz

답안 #681379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681379 2023-01-12T21:46:10 Z Nafeeszx Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 443 ms 37728 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;

const ll mod = 1e9 + 7, MOD = 998244353;

void setIO(string name = "") { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(name.size()){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct item{
    ll l, r, dp[2][2];
};

struct segtree{

    int size;
    vector<item> values;

	item neut = {0, 0, {{0,0}, {0,0}}};

    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        values.assign(2 * size, neut);
    }

	item single (int v) {
		return {v, v, {{0, 0}, {0, abs(v)}}};
	}

	item merge(item &x, item &y) {
		item res;
        res.l = x.l;
        res.r = y.r;
       
        F0R(l, 2) F0R(r, 2) {
            res.dp[l][r] = 0;
            F0R(o, 2) F0R(m, 2) {
            if(m == 1 && o == 1 && (x.r >= 0) != (y.l >= 0)) continue;
            res.dp[l][r] = max(res.dp[l][r], x.dp[l][m] + y.dp[o][r]);
            }
        }
        return res;
	}

    void build(vector<ll> &a, int x, int lx, int rx) {
        if(rx - lx == 1) {
            if(lx < (int)a.size()) {
                values[x] = single(a[lx]);
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void build(vector<ll> &a) {
        build(a, 0, 0, size);
    }

    void set(int i, ll v, int x, int lx, int rx){
        if(rx - lx == 1){
            values[x] = single(v);
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m){
            set(i, v, 2 * x + 1, lx, m);
        } else {
            set(i, v, 2 * x + 2, m, rx);
        }
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void set(int i, ll v){
        set(i, v, 0, 0, size);
    } 

    item calc(int l, int r, int x, int lx, int rx){
        if(lx >= r || rx <= l) return neut;
        if(l <= lx && r >= rx) return values[x];
        int m = (lx + rx) / 2;
        item s1 = calc(l, r, 2 * x + 1, lx, m);
        item s2 = calc(l, r, 2 * x + 2, m, rx);
        return merge(s1, s2);
    } 

    item calc(int l, int r){
        return calc(l, r, 0, 0, size);
    }
};

int main() 
{	
	setIO();
    int n, q; cin >> n >> q; 
    vector<ll> a(n), d(n-1);
    F0R(i, n) cin >> a[i];
    F0R(i, n-1) {
        d[i] = a[i+1] - a[i];
    }
    segtree S;
    S.init(n-1);
    S.build(d);
    //item res = S.values[0];
        /*int mx = 0;
        F0R(i, 2) F0R(j, 2) {
            mx = max(mx, res.dp[i][j]);
        }
        cout << mx << '\n';*/
        //cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
    while(q--) {
        ll l, r, x;
        cin >> l >> r >> x;
        l -= 2;
        r--;
        if(l >= 0) {d[l] = d[l] + x; S.set(l, d[l]);}// cout << d[l] << " ";}
        if(r < n-1){d[r] = d[r] - x; S.set(r, d[r]);}
        //cout << d[r ] << " ";}
        //cout << d[l] << d[r] << " ";
        
       
        item res = S.values[0];
        ll mx = 0;
        F0R(i, 2) F0R(j, 2) {
            mx = max(mx, res.dp[i][j]);
        }
        cout << mx << "\n";
        //cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
    }
	return 0;
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 896 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 896 KB Output is correct
13 Correct 407 ms 37224 KB Output is correct
14 Correct 425 ms 37204 KB Output is correct
15 Correct 409 ms 37108 KB Output is correct
16 Correct 394 ms 37096 KB Output is correct
17 Correct 443 ms 37040 KB Output is correct
18 Correct 370 ms 37728 KB Output is correct