oj.uz

Submission #379394

# Submission time Handle Problem Language Result Execution time Memory
379394 2021-03-18T06:01:18 Z limabeans Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 164608 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 2e5+10;



int n,q;
ll a[maxn];


//00
//01
//10
//11

ll sgn(ll x) {
    if (x==0) return 0;
    if (x>0) return 1;
    if (x<0) return -1;
    
    assert(false);
    return 1;
}

struct node {
    ll dx;
    map<pair<int,int>,ll> dp;
    node() {
	dx = 0;
	dp[{sgn(0),sgn(0)}] = abs(0);
    }
    node(ll x) {
	dx = x;
	dp[{sgn(0),sgn(0)}] = abs(0);
	dp[{sgn(x),sgn(x)}] = abs(x);
    }
};


bool mergable(pair<int,int> p, pair<int,int> q) {
    return p.second*q.first >= 0;
}

node merge(node x, node y) {
    node res = x;
    for (auto p: y.dp) {
	res.dp[p.first] = max(res.dp[p.first], p.second);
    }
    for (auto p: x.dp) {
	for (auto q: y.dp) {
	    if (mergable(p.first,q.first)) {
		pair<int,int> ends = {p.first.first,q.first.second};
		res.dp[ends] = max(res.dp[ends], p.second+q.second);
	    }
	}
    }
    return res;
}

node t[4*maxn];

void upd(int v, int tl, int tr, int i, ll dx) {
    if (tl==tr) {
	ll prev = t[v].dx;
	t[v] = node(prev+dx);
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,dx);
	} else {
	    upd(2*v+1,tm+1,tr,i,dx);
	}
	t[v]=merge(t[2*v],t[2*v+1]);
    }
}


void build(int v, int tl, int tr) {
    if (tl==tr) {
	if (tl>1) {
	    t[v]=node(a[tl]-a[tl-1]);
	} else {
	    t[v]=node();
	}
    } else {
	int tm = (tl+tr)/2;
	build(2*v,tl,tm);
	build(2*v+1,tm+1,tr);
	t[v]=merge(t[2*v],t[2*v+1]);
    }
}

node qry(int v, int tl, int tr, int l, int r) {
    assert(0);
    if (l>tr || r<tl) {
	return node();
    } else if (l<=tl && tr<=r) {
	return t[v];
    } else {
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
    }
}

void update(int l, int r, ll dx) {
    if (l>1) {
	upd(1,1,n,l,dx);
    }
    if (r<n) {
	upd(1,1,n,r+1,-dx);
    }

}

ll solve() {
    ll res = 0;
    for (auto p: t[1].dp) {
	res = max(res, p.second);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    build(1,1,n);

    while (q--) {
	int l,r,dx;
	cin>>l>>r>>dx;
	update(l,r,dx);
	cout<<solve()<<"\n";
    }
    
    
    return 0;
}

/*
ll solve() {
    ll dp0 = 0;
    ll dp1 = 0;
    
    ll diff0 = 0;
    for (int i=2; i<=n; i++) {
	ll diff = a[i]-a[i-1];
	if (diff0*diff>=0) {
	    ll _dp0 = max(dp0,dp1);
	    ll _dp1 = max(dp1,dp0)+abs(diff);
	    dp0 = _dp0;
	    dp1 = _dp1;
	} else {
	    ll _dp0 = max(dp0,dp1);
	    ll _dp1 = dp0+abs(diff);
	    dp0 = _dp0;
	    dp1 = _dp1;
	}
	diff0 = diff;
    }
    return max(dp0, dp1);
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 94464 KB Output is correct
2 Correct 102 ms 94336 KB Output is correct
3 Correct 115 ms 94328 KB Output is correct
4 Correct 102 ms 94444 KB Output is correct
5 Correct 103 ms 94316 KB Output is correct
6 Correct 104 ms 94316 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 94464 KB Output is correct
2 Correct 102 ms 94336 KB Output is correct
3 Correct 115 ms 94328 KB Output is correct
4 Correct 102 ms 94444 KB Output is correct
5 Correct 103 ms 94316 KB Output is correct
6 Correct 104 ms 94316 KB Output is correct
7 Correct 313 ms 95596 KB Output is correct
8 Correct 311 ms 95724 KB Output is correct
9 Correct 323 ms 95724 KB Output is correct
10 Correct 310 ms 95648 KB Output is correct
11 Correct 318 ms 95596 KB Output is correct
12 Correct 295 ms 95724 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 94464 KB Output is correct
2 Correct 102 ms 94336 KB Output is correct
3 Correct 115 ms 94328 KB Output is correct
4 Correct 102 ms 94444 KB Output is correct
5 Correct 103 ms 94316 KB Output is correct
6 Correct 104 ms 94316 KB Output is correct
7 Correct 313 ms 95596 KB Output is correct
8 Correct 311 ms 95724 KB Output is correct
9 Correct 323 ms 95724 KB Output is correct
10 Correct 310 ms 95648 KB Output is correct
11 Correct 318 ms 95596 KB Output is correct
12 Correct 295 ms 95724 KB Output is correct
13 Execution timed out 2072 ms 164608 KB Time limit exceeded
14 Halted 0 ms 0 KB -