Submission #547666

#TimeUsernameProblemLanguageResultExecution timeMemory
547666tmn2005Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
385 ms15728 KiB
#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<bits/stdc++.h> using namespace __gnu_pbds; using namespace std; typedef long long ll; #define fr first #define sc second #define mk make_pair #define pb push_back #define pob pop_back #define pf push_front #define pof pop_front #define int long long #define pii pair<int,int> #define piii pair<int,pii> #define all(s) s.begin(), s.end() #define allr(s) s.rbegin(), s.rend() #define NeedForSpeed ios::sync_with_stdio(0), cin.tie(0) #define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> const int N = 2e5 + 12; int n, m, k, a[N], b, c, d, x, y, l, r, ans, t[N<<2]; int get(int v, int l, int r, int i){ if(l == r) return t[v]; int m = l + r >> 1; if(i <= m) return t[v] + get(v*2, l, m, i); else return t[v] + get(v*2+1, m+1, r, i); } void update(int v, int l, int r, int ql, int qr, int add){ if(r < ql || qr < l) return; if(ql <= l && r <= qr){ t[v] += add; } else{ int m = l + r >> 1; update(v*2, l, m, ql, qr, add); update(v*2+1, m+1, r, ql, qr, add); } } void solve(){ cin>>n>>m>>x>>y; cin>>a[0];for(int i=1; i<=n; i++)cin>>a[i]; for(int i=0; i<n; i++){ if(a[i] < a[i+1])ans -= (x * abs(a[i] - a[i+1])); else ans += (y * abs(a[i] - a[i+1])); } while(m--){ int l, r, z; cin>>l>>r>>z; int s = a[l-1] + get(1, 0, n, l-1); int t = a[l] + get(1, 0, n, l); if(s < t)ans += (x * abs(s - t)); else ans -= (y * abs(s - t)); s = a[r] + get(1, 0, n, r); t = a[r+1] + get(1, 0, n, r+1); if(s < t)ans += (x * abs(s - t)); else ans -= (y * abs(s - t)); update(1, 0, n, l, r, z); s = a[l-1] + get(1, 0, n, l-1); t = a[l] + get(1, 0, n, l); if(s < t)ans -= (x * abs(s - t)); else ans += (y * abs(s - t)); s = a[r] + get(1, 0, n, r); t = a[r+1] + get(1, 0, n, r+1); if(s < t)ans -= (x * abs(s - t)); else ans += (y * abs(s - t)); cout<<ans<<"\n"; } } main(){ NeedForSpeed; int T = 1; // cin >> T; while(T--){ solve(); } return 0; }

Compilation message (stderr)

foehn_phenomena.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m = l + r >> 1;
      |          ~~^~~
foehn_phenomena.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int m = l + r >> 1;
      |           ~~^~~
foehn_phenomena.cpp: At global scope:
foehn_phenomena.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...