oj.uz

답안 #232733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232733 2020-05-18T02:27:43 Z kym Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 549 ms 32248 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int ll
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
string cts(char x) {string t(1,x); return t;}
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, T b) { a = max(a, b); }
template <typename T> void chmin(T& a, T b) { a = min(a, b); }
const int MAXN = 2e5+5;
#ifndef LOCAL
#define cerr if(0)cout
#endif
int A[MAXN];
struct node {
	int s,e,m,val,lazy;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e;
		m = (s+e)/2;
		lazy = 0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		} else {
			val=A[s];
		}
	}
	int value(){
		if(lazy==0)return val;
		val+=lazy;
		if(s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
		return val;
	}
	void update(int x, int y, int nval) {
		value();
		if(s==x&&e==y){
			lazy+=nval;
			return;
		}
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else l->update(x,m,nval),r->update(m+1,y,nval);
	}
	int get(int x) {
		value();
		if(s==e)return val;
		if(x>m)return r->get(x);
		else return l->get(x);
	}
} *seg;
ll n,Q,s,t;

ll calc(ll now, ll last) {
	ll res = 0;
	if(last<now){
		res-=s*(now-last);
	} else {
		res+=t*(last-now);
	}
	return res;
}

int32_t main() 
{
	IAMSPEED
	cin>>n>>Q>>s>>t;
	FOR(i,0,n)cin>>A[i];
	seg=new node(0,n);
	ll ans = 0;
	FOR(i,1,n){
		ll now = A[i], last = A[i-1];
		ans+=calc(now,last);
	}
	//db(ans);
	while(Q--){
		int l,r,nval; cin >> l >> r >> nval;
		ans-=calc(seg->get(l),seg->get(l-1));
		if(r!=n){
			ans-=calc(seg->get(r+1),seg->get(r));
		}
		ans+=calc(nval+seg->get(l),seg->get(l-1));
		if(r!=n){
			ans+=calc(seg->get(r+1),seg->get(r)+nval);
		}
		seg->update(l,r,nval);
		cout << ans << '\n';
	}
}

/* DEBUG
** Array bounds
** Overflow
** Edge cases
** do something 
** write stuff down
*/

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 9 ms 768 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 7 ms 640 KB Output is correct
16 Correct 6 ms 640 KB Output is correct
17 Correct 6 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 28408 KB Output is correct
2 Correct 526 ms 29048 KB Output is correct
3 Correct 524 ms 29560 KB Output is correct
4 Correct 549 ms 28932 KB Output is correct
5 Correct 527 ms 30712 KB Output is correct
6 Correct 221 ms 31224 KB Output is correct
7 Correct 218 ms 31224 KB Output is correct
8 Correct 429 ms 31096 KB Output is correct
9 Correct 442 ms 31608 KB Output is correct
10 Correct 432 ms 30328 KB Output is correct
11 Correct 248 ms 31224 KB Output is correct
12 Correct 217 ms 31608 KB Output is correct
13 Correct 214 ms 31992 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 9 ms 768 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 7 ms 640 KB Output is correct
16 Correct 6 ms 640 KB Output is correct
17 Correct 6 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 535 ms 28408 KB Output is correct
23 Correct 526 ms 29048 KB Output is correct
24 Correct 524 ms 29560 KB Output is correct
25 Correct 549 ms 28932 KB Output is correct
26 Correct 527 ms 30712 KB Output is correct
27 Correct 221 ms 31224 KB Output is correct
28 Correct 218 ms 31224 KB Output is correct
29 Correct 429 ms 31096 KB Output is correct
30 Correct 442 ms 31608 KB Output is correct
31 Correct 432 ms 30328 KB Output is correct
32 Correct 248 ms 31224 KB Output is correct
33 Correct 217 ms 31608 KB Output is correct
34 Correct 214 ms 31992 KB Output is correct
35 Correct 529 ms 29956 KB Output is correct
36 Correct 524 ms 31200 KB Output is correct
37 Correct 539 ms 31992 KB Output is correct
38 Correct 539 ms 31864 KB Output is correct
39 Correct 545 ms 31864 KB Output is correct
40 Correct 527 ms 31864 KB Output is correct
41 Correct 545 ms 31652 KB Output is correct
42 Correct 533 ms 31736 KB Output is correct
43 Correct 532 ms 31304 KB Output is correct
44 Correct 523 ms 31540 KB Output is correct
45 Correct 528 ms 31224 KB Output is correct
46 Correct 528 ms 31864 KB Output is correct
47 Correct 217 ms 31864 KB Output is correct
48 Correct 230 ms 32248 KB Output is correct
49 Correct 505 ms 31224 KB Output is correct
50 Correct 247 ms 31864 KB Output is correct
51 Correct 220 ms 31864 KB Output is correct
52 Correct 294 ms 31864 KB Output is correct