Submission #227934

#	Time	Username	Problem	Language	Result	Execution time	Memory
227934		dvdg6566	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	869 ms	11896 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 301000;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll N,M,a,b,A,B;
ll fw[MAXN];
ll ans;

void up(ll x, ll y, ll v){
	--x;
	for(;y;y-=y&(-y))fw[y]+=v;
	for(;x;x-=x&(-x))fw[x]-=v;
}

ll query(ll x){
	if(x==0)return 0;
	ll res=0;
	for(;x<=N;x+=x&(-x))res+=fw[x];
	return res;
}

ll ask(ll a, ll b){
	// cerr<<a<<' '<<b<<'\n';
	if(a<b)return A*(a-b);
	else return B*(a-b);
}

int main(){
	cin>>N>>M>>A>>B;
	cin>>a;
	// cerr<<ask(4,8)<<'\n';
	for (ll i=1;i<=N;++i){
		cin>>a;
		ans+=ask(b,a);
		up(i,i,a);
		b=a;
	}
	// cout<<ans<<'\n';
	// return 0;
	for (ll i=0;i<M;++i){
		ll a,b,c,d,h;
		cin>>a>>b>>h;
		ans-=ask(query(a-1),query(a));
		// cerr<<(b==N)<<' '<<query(b)<<' '<<query(b+1)<<'\n';
		if(b!=N)ans-=ask(query(b),query(b+1));
		// cerr<<"I "<<ans<<'\n';
		up(a,b,h);
		ans+=ask(query(a-1),query(a));
		if(b!=N)ans+=ask(query(b),query(b+1));
		cout<<ans<<'\n';
		// for(ll i=1;i<=N;++i)cout<<query(i)<<' ';cout<<'\n';
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:56:10: warning: unused variable 'c' [-Wunused-variable]
   ll a,b,c,d,h;
          ^
foehn_phenomena.cpp:56:12: warning: unused variable 'd' [-Wunused-variable]
   ll a,b,c,d,h;
            ^

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60