oj.uz

Submission #100009

# Submission time Handle Problem Language Result Execution time Memory
100009 2019-03-09T06:25:21 Z ryansee Foehn Phenomena (JOI17_foehn_phenomena) C++14
100 / 100
 242 ms 13120 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890l
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define space " "
#define cbr cout << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, q, s, t,A[MAXN],ans,fw[MAXN];
struct fen
{
	void update(ll x, ll y, ll nv)
	{
		for(; x <= n; x+=x&(-x)) fw[x] += nv;
		++y;
		for(; y<=n; y+=y&(-y)) fw[y]-=nv;
	}
	ll sum(ll x) { /* point */ ll res = 0; for(; x; x-=x&(-x)) res += fw[x]; return res; }
} fen;
int main()
{
	FAST
	cin>>n>>q>>s>>t;
	for(ll i = 0; i <= n; i++) cin>>A[i];
	FOR(i,0,n) 
	{
		if(A[i] < A[i+1]) ans -= (s*(A[i+1]-A[i]));
		else ans += (t*(A[i]-A[i+1]));
	}
	FOR(i,1,n+1)fen.update(i,i,A[i]);
	for(ll i=0;i<q;i++)
	{
			ll a, b, x;cin>>a>>b>>x;
			{
				ll b4 = fen.sum(a-1); ll aft = fen.sum(a);
				if(b4 < aft) ans += (s*(aft-b4));
				else ans -= (t*(b4-aft));
			}
			if(b != n)
			{
				ll b4 = fen.sum(b); ll aft = fen.sum(b+1);
				if(b4 < aft) ans += (s*(aft-b4));
				else ans -= (t*(b4-aft));
			}
			fen.update(a,b,x);
			// if(a != 1)
			{
				ll b4 = fen.sum(a-1); ll aft = fen.sum(a);
				if(b4 < aft) ans -= (s*(aft-b4));
				else ans += (t*(b4-aft));
			}
			if(b != n)
			{
				ll b4 = fen.sum(b); ll aft = fen.sum(b+1);
				if(b4 < aft) ans -= (s*(aft-b4));
				else ans += (t*(b4-aft));
			}
			cout<<ans<<"\n";
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 432 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 520 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 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 231 ms 10256 KB Output is correct
2 Correct 190 ms 10884 KB Output is correct
3 Correct 237 ms 11480 KB Output is correct
4 Correct 196 ms 11000 KB Output is correct
5 Correct 174 ms 12084 KB Output is correct
6 Correct 137 ms 11044 KB Output is correct
7 Correct 114 ms 10956 KB Output is correct
8 Correct 189 ms 12004 KB Output is correct
9 Correct 178 ms 12200 KB Output is correct
10 Correct 204 ms 10864 KB Output is correct
11 Correct 128 ms 10904 KB Output is correct
12 Correct 125 ms 11668 KB Output is correct
13 Correct 148 ms 11920 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 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 432 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 520 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 231 ms 10256 KB Output is correct
23 Correct 190 ms 10884 KB Output is correct
24 Correct 237 ms 11480 KB Output is correct
25 Correct 196 ms 11000 KB Output is correct
26 Correct 174 ms 12084 KB Output is correct
27 Correct 137 ms 11044 KB Output is correct
28 Correct 114 ms 10956 KB Output is correct
29 Correct 189 ms 12004 KB Output is correct
30 Correct 178 ms 12200 KB Output is correct
31 Correct 204 ms 10864 KB Output is correct
32 Correct 128 ms 10904 KB Output is correct
33 Correct 125 ms 11668 KB Output is correct
34 Correct 148 ms 11920 KB Output is correct
35 Correct 221 ms 10392 KB Output is correct
36 Correct 187 ms 11812 KB Output is correct
37 Correct 193 ms 12624 KB Output is correct
38 Correct 238 ms 12576 KB Output is correct
39 Correct 193 ms 12428 KB Output is correct
40 Correct 242 ms 12428 KB Output is correct
41 Correct 231 ms 12272 KB Output is correct
42 Correct 193 ms 12312 KB Output is correct
43 Correct 193 ms 11644 KB Output is correct
44 Correct 192 ms 12004 KB Output is correct
45 Correct 168 ms 12076 KB Output is correct
46 Correct 173 ms 13120 KB Output is correct
47 Correct 191 ms 11624 KB Output is correct
48 Correct 133 ms 11772 KB Output is correct
49 Correct 181 ms 10744 KB Output is correct
50 Correct 126 ms 11512 KB Output is correct
51 Correct 163 ms 11964 KB Output is correct
52 Correct 138 ms 11712 KB Output is correct