oj.uz

Submission #875592

# Submission time Handle Problem Language Result Execution time Memory
875592 2023-11-20T06:25:24 Z ReLice Foehn Phenomena (JOI17_foehn_phenomena) C++14
10 / 100
 374 ms 23732 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=2e5+7;
const ld eps=1e-9;

vector<ll> t(N*4);
ll add[N*4],a[N],vv[N];
void build(ll v,ll tl,ll tr){
	if(tl==tr){
		t[v]=vv[tl];
		return;
	}
	ll tm=(tl+tr)/2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
}
void push(ll v,ll tl,ll tr){
	if(tl!=tr){
		add[v*2]+=add[v];
		add[v*2+1]+=add[v];
	}
	else t[v]+=add[v];
	add[v]=0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll val){
	push(v,tl,tr);
	if(tl>r || tr<l) return;
	if(l<=tl && tr<=r){
		add[v]+=val;
		push(v,tl,tr);
		return;
	}
	ll tm=(tl+tr)/2;
	upd(v*2,tl,tm,l,r,val);
	upd(v*2+1,tm+1,tr,l,r,val);
}
ll get(ll v,ll tl,ll tr,ll pos){
	push(v,tl,tr);
	if(tl>pos || tr<pos)return 0ll;
	if(tl==tr){
		return t[v];
	}
	ll tm=(tl+tr)/2;
	return max(get(v*2,tl,tm,pos),get(v*2+1,tm+1,tr,pos));
}
void solve(){
    ll i,j;
    ll n,q,x,y;
    cin>>n>>q>>x>>y;
    for(i=1;i<=n+1;i++){
		cin>>vv[i];
		if(i>1){
			a[i]=a[i-1]+(vv[i-1]-vv[i]<0 ? (vv[i-1]-vv[i])*x : (vv[i-1]-vv[i])*y);
		}
	}
	build(1,1,n+1);
	ll sum=a[n+1];
	ll l,r,b;
	n++;
	for(i=0;i<q;i++){
		cin>>l>>r>>b;
		if(r+1==n){
			ll l1=get(1,1,n,l),l2=get(1,1,n,l+1);
			ll prev=l1-l2,cur=l1-(l2+b);
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			upd(1,1,n,l+1,r+1,b);
		}else{
			ll l1=get(1,1,n,l),l2=get(1,1,n,l+1),r1=get(1,1,n,r+1),r2=get(1,1,n,r+2);
			ll prev=l1-l2,cur=l1-(l2+b);
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			prev=r1-r2,cur=(r1+b)-r2;
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			upd(1,1,n,l+1,r+1,b);
		}
		cout<<sum<<endl;
	}
		
		
}

signed main(){
    start();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*









*/

Compilation message

foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:71:10: warning: unused variable 'j' [-Wunused-variable]
   71 |     ll i,j;
      |          ^
foehn_phenomena.cpp: In function 'void fre(std::string)':
foehn_phenomena.cpp:19:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:19:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6744 KB Output is correct
2 Incorrect 4 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 21844 KB Output is correct
2 Correct 374 ms 22564 KB Output is correct
3 Correct 307 ms 22944 KB Output is correct
4 Correct 300 ms 22348 KB Output is correct
5 Correct 299 ms 23636 KB Output is correct
6 Correct 159 ms 20560 KB Output is correct
7 Correct 160 ms 20500 KB Output is correct
8 Correct 265 ms 23524 KB Output is correct
9 Correct 252 ms 23732 KB Output is correct
10 Correct 254 ms 22612 KB Output is correct
11 Correct 219 ms 20540 KB Output is correct
12 Correct 155 ms 21076 KB Output is correct
13 Correct 160 ms 21456 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6744 KB Output is correct
2 Incorrect 4 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -