oj.uz

답안 #857033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
857033 2023-10-05T09:15:25 Z arashMLG Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 448 ms 17748 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

//https://quera.org/profile/4dykhk

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 2e5 + 23;
const int sq = 450;
const ll mod = 1e9+7; // 998244353
const int LOG = 23;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define F           first
#define S           second
#define pb          push_back
#define ms(x,y)     memset((x) , (y) , sizeof (x))
#define done        return cout<<endl , 0;
#define kill(x)     cout<<x<<endl, exit(0);
#define isIn(x,s,e) ((x) >= (s) && (x) <= e)
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define pc(x)       __builtin_popcount(x)
#define ctz(x)      __builtin_ctz(x)
#define MinHeap(x)  priority_queue<x, vector<x> , greater<x> >
#define MaxHeap(x)  priority_queue<x, vector<x>>
#define lc          (v << 1)
#define rc          ((v<<1) |1)
#define int      ll

ll pw(ll a, ll b, ll md = mod){ll res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n;
int a[N];
int t[N<<2];

void build(int v=1,int tl=0,int tr=n+1) {
	if(tr-tl ==1) {
		t[v] = a[tl];
		return;
	}
	int mid=(tl+tr)/2;
	build(lc,tl,mid);
	build(rc,mid,tr);
}

void shift(int v) {
	if(t[v] == 0) return;
	t[lc] += t[v];
	t[rc] += t[v];
	t[v] = 0;
}

void upd(int l,int r,int x,int v =1,int tl = 0 ,int tr = n+1) {
	if(l > r) return;
	if(l == tl && r == tr-1) {
		t[v] += x;
		return;
	}
	shift(v);
	int mid=(tl+tr)/2;
	upd(l,min(mid-1,r),x,lc,tl,mid);
	upd(max(l,mid),r,x,rc,mid,tr);
}

int get(int pos,int v=1,int tl = 0, int tr =n+1) {
	if(tr-tl ==1) return t[v];
	shift(v);
	int mid=(tl+tr)/2;
	if(pos<mid)
		return get(pos,lc,tl,mid);
	else
		return get(pos,rc,mid,tr);
}

/*void print(__int128_t x) {
	string s;
	while(x > 0) {
		s.pb(x%10 + '0');
		x/=10;
	}
	if(sz(s) ==0) s.pb('0');
	reverse(all(s));
	cout<<s<<'\n';
}*/

int q,s,l;

int val(int i) {
	if(i == n) return 0;
	if(get(i) < get(i+1)) {
		return -(get(i+1)-get(i))*s;
	} else {
		return (get(i) - get(i+1))*l;
	}
}


int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q>>s>>l;
	for(int i = 0; i <= n ;i ++) cin>>a[i];
	
	build();
	int sum =0;
	for(int i = 0 ; i < n; i ++) {
		if(a[i] < a[i+1]) {
			sum -= (a[i+1]-a[i])*s;
		} else {
			sum += (a[i] - a[i+1])*l;
		}
	}
	debug(sum);
	while(q--) {
		int l,r,x; cin>>l>>r>>x;
		sum -= val(l-1);
		sum -= val(r);
		debug(val(l-1),val(r));
		upd(l,r,x);
		sum += val(l-1);
		sum += val(r);
		cout<<sum << '\n';
	}
    done;
}

Compilation message

foehn_phenomena.cpp: In function 'int32_t main()':
foehn_phenomena.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
foehn_phenomena.cpp:126:2: note: in expansion of macro 'debug'
  126 |  debug(sum);
      |  ^~~~~
foehn_phenomena.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
foehn_phenomena.cpp:131:3: note: in expansion of macro 'debug'
  131 |   debug(val(l-1),val(r));
      |   ^~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 4 ms 2604 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 4 ms 2476 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2620 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 4 ms 2396 KB Output is correct
12 Correct 4 ms 2612 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 2 ms 2396 KB Output is correct
15 Correct 3 ms 2600 KB Output is correct
16 Correct 2 ms 2648 KB Output is correct
17 Correct 2 ms 2392 KB Output is correct
18 Correct 2 ms 2648 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 15188 KB Output is correct
2 Correct 416 ms 15576 KB Output is correct
3 Correct 438 ms 16216 KB Output is correct
4 Correct 413 ms 15764 KB Output is correct
5 Correct 411 ms 16704 KB Output is correct
6 Correct 144 ms 15580 KB Output is correct
7 Correct 135 ms 15668 KB Output is correct
8 Correct 328 ms 16540 KB Output is correct
9 Correct 328 ms 16980 KB Output is correct
10 Correct 335 ms 15568 KB Output is correct
11 Correct 196 ms 15440 KB Output is correct
12 Correct 133 ms 16128 KB Output is correct
13 Correct 150 ms 16720 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 4 ms 2604 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 4 ms 2476 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2620 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 4 ms 2396 KB Output is correct
12 Correct 4 ms 2612 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 2 ms 2396 KB Output is correct
15 Correct 3 ms 2600 KB Output is correct
16 Correct 2 ms 2648 KB Output is correct
17 Correct 2 ms 2392 KB Output is correct
18 Correct 2 ms 2648 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 415 ms 15188 KB Output is correct
23 Correct 416 ms 15576 KB Output is correct
24 Correct 438 ms 16216 KB Output is correct
25 Correct 413 ms 15764 KB Output is correct
26 Correct 411 ms 16704 KB Output is correct
27 Correct 144 ms 15580 KB Output is correct
28 Correct 135 ms 15668 KB Output is correct
29 Correct 328 ms 16540 KB Output is correct
30 Correct 328 ms 16980 KB Output is correct
31 Correct 335 ms 15568 KB Output is correct
32 Correct 196 ms 15440 KB Output is correct
33 Correct 133 ms 16128 KB Output is correct
34 Correct 150 ms 16720 KB Output is correct
35 Correct 421 ms 15184 KB Output is correct
36 Correct 421 ms 16540 KB Output is correct
37 Correct 432 ms 17532 KB Output is correct
38 Correct 437 ms 17168 KB Output is correct
39 Correct 423 ms 17172 KB Output is correct
40 Correct 417 ms 17236 KB Output is correct
41 Correct 448 ms 16936 KB Output is correct
42 Correct 423 ms 17260 KB Output is correct
43 Correct 418 ms 16284 KB Output is correct
44 Correct 419 ms 16684 KB Output is correct
45 Correct 418 ms 16976 KB Output is correct
46 Correct 416 ms 17748 KB Output is correct
47 Correct 135 ms 16548 KB Output is correct
48 Correct 190 ms 16168 KB Output is correct
49 Correct 407 ms 15348 KB Output is correct
50 Correct 204 ms 16328 KB Output is correct
51 Correct 141 ms 16780 KB Output is correct
52 Correct 208 ms 16212 KB Output is correct