oj.uz

Submission #102934

# Submission time Handle Problem Language Result Execution time Memory
102934 2019-03-28T07:30:06 Z RockyB Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 314 ms 13368 KB 
/// In The Name Of God

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, q, s, t;
ll a[N];

struct tree {
	ll f[N];
	void upd(int p, int x) {
		for (; p < N; p |= p + 1) f[p] += x;
	}
	ll get(int p) {
		ll res = 0;
		for (; p >= 0; p = (p & (p + 1)) - 1) res += f[p];
		return res;
	}
} f;

ll ans;
void upd(int p, int x) {
	if (p < 0 || p >= n) return;
	a[p] = f.get(p), a[p + 1] = f.get(p + 1);
	if (a[p] < a[p + 1]) ans -= (abs(a[p + 1] - a[p]) * s) * x;
	else ans += (abs(a[p] - a[p + 1]) * t) * x;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> q >> s >> t;
	rep(i, 0, n) {
		cin >> a[i];
		f.upd(i + 1, -a[i]);
		f.upd(i, a[i]);
	}
	rep(i, 0, n - 1) {
		if (a[i] < a[i + 1]) ans -= abs(a[i + 1] - a[i]) * s;
		else ans += abs(a[i] - a[i + 1]) * t;
	}
	rep(i, 1, q) {
		int l, r, x;
		cin >> l >> r >> x;
		upd(l - 1, -1);
		upd(r, -1);
		f.upd(l, x);
		f.upd(r + 1, -x);
		upd(l - 1, 1);
		upd(r, 1);

		/*
		rep(j, l, r) a[j] += x;
		int ans = 0;
		rep(j, 0, n - 1) {
			if (a[j] < a[j + 1]) ans -= (a[j + 1] - a[j]) * s;
			else ans += (a[j] - a[j + 1]) * t;
		}*/
		cout << ans << nl;
	}

	ioi
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4896 KB Output is correct
2 Correct 237 ms 5568 KB Output is correct
3 Correct 209 ms 6136 KB Output is correct
4 Correct 242 ms 5404 KB Output is correct
5 Correct 314 ms 12136 KB Output is correct
6 Correct 150 ms 11216 KB Output is correct
7 Correct 204 ms 11128 KB Output is correct
8 Correct 221 ms 11912 KB Output is correct
9 Correct 204 ms 12152 KB Output is correct
10 Correct 233 ms 11000 KB Output is correct
11 Correct 134 ms 11104 KB Output is correct
12 Correct 143 ms 11624 KB Output is correct
13 Correct 139 ms 12064 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 198 ms 4896 KB Output is correct
23 Correct 237 ms 5568 KB Output is correct
24 Correct 209 ms 6136 KB Output is correct
25 Correct 242 ms 5404 KB Output is correct
26 Correct 314 ms 12136 KB Output is correct
27 Correct 150 ms 11216 KB Output is correct
28 Correct 204 ms 11128 KB Output is correct
29 Correct 221 ms 11912 KB Output is correct
30 Correct 204 ms 12152 KB Output is correct
31 Correct 233 ms 11000 KB Output is correct
32 Correct 134 ms 11104 KB Output is correct
33 Correct 143 ms 11624 KB Output is correct
34 Correct 139 ms 12064 KB Output is correct
35 Correct 226 ms 10440 KB Output is correct
36 Correct 248 ms 12024 KB Output is correct
37 Correct 254 ms 12676 KB Output is correct
38 Correct 272 ms 12608 KB Output is correct
39 Correct 301 ms 12536 KB Output is correct
40 Correct 223 ms 12488 KB Output is correct
41 Correct 224 ms 12408 KB Output is correct
42 Correct 262 ms 12536 KB Output is correct
43 Correct 274 ms 11656 KB Output is correct
44 Correct 290 ms 12148 KB Output is correct
45 Correct 259 ms 12160 KB Output is correct
46 Correct 236 ms 13368 KB Output is correct
47 Correct 141 ms 11640 KB Output is correct
48 Correct 203 ms 11768 KB Output is correct
49 Correct 221 ms 10776 KB Output is correct
50 Correct 154 ms 11512 KB Output is correct
51 Correct 194 ms 12008 KB Output is correct
52 Correct 178 ms 11828 KB Output is correct