Submission #167856

#	Time	Username	Problem	Language	Result	Execution time	Memory
167856		theStaticMind	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	200 ms	13148 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
struct Fenwick{
      vector<int> bit;
      int size;
      void modify(int j,int v){
            j++;
            for(;j<size;j+=j&-j)bit[j]+=v;
      }
      int query(int j){
            j++;
            if(j>=size)j--;
            int v=0;
            for(;j>0;j-=j&-j)v+=bit[j];
            return v;
      }
      Fenwick(int s){
            size=s;
            bit=vector<int>(s,0);
      }
};
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,q,dec,inc;
      cin>>n>>q>>dec>>inc;
      Fenwick bit(n+2);
      vector<int>arr(n+1,0);
      for(int i=0;i<=n;i++)cin>>arr[i];
      arr.pb(arr.back());
      int sum=0;
      for(int i=1;i<=n;i++){
            int diff=arr[i]-arr[i-1];
            if(diff>=0)sum-=diff*dec;
            else sum-=diff*inc;
      }
      while(q--){
            int l,r,x;
            cin>>l>>r>>x;
            int dl=0,dr=0;
            dl=arr[l]+bit.query(l)-arr[l-1]-bit.query(l-1);
            dr=arr[r+1]+bit.query(r+1)-arr[r]-bit.query(r);
            bit.modify(r+1,-x);
            bit.modify(l,x);
            int L=bit.query(l)+arr[l];
            int R=bit.query(r)+arr[r];
            int dL=0,dR=0;
            dL=arr[l]+bit.query(l)-arr[l-1]-bit.query(l-1);
            dR=arr[r+1]+bit.query(r+1)-arr[r]-bit.query(r);
            if(dl>=0)sum+=dl*dec;
            else sum+=dl*inc;
            if(dr>=0)sum+=dr*dec;
            else sum+=dr*inc;
            if(dL>=0)sum-=dL*dec;
            else sum-=dL*inc;
            if(dR>=0)sum-=dR*dec;
            else sum-=dR*inc;
            cout<<sum<<"\n";
      }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int32_t main()':
foehn_phenomena.cpp:55:17: warning: unused variable 'L' [-Wunused-variable]
             int L=bit.query(l)+arr[l];
                 ^
foehn_phenomena.cpp:56:17: warning: unused variable 'R' [-Wunused-variable]
             int R=bit.query(r)+arr[r];
                 ^

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