Submission #245292

#	Time	Username	Problem	Language	Result	Execution time	Memory
245292		kimbj0709	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	872 ms	18540 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 200050
vector<int> seg(maxn*4,0),lazy(maxn*4,0);
vector<int> vect1;
void build(int node,int start,int end){
  if(start==end){
    seg[node] = vect1[start];
    return;
  }
  int mid = (start+end)/2;
  build(node*2+1,start,mid);
  build(node*2+2,mid+1,end);
}
void update(int node,int start,int end,int rangemin,int rangemax,int val){
    if(lazy[node]!=0){
      seg[node] += lazy[node];
      if(start!=end){
        lazy[node*2+1] += lazy[node];
        lazy[node*2+2] += lazy[node];
      }
      lazy[node] = 0;
    }
    if(start>rangemax||end<rangemin){
        return;
    }
    else if(start>=rangemin&&end<=rangemax){
        seg[node] += val;
        if(start!=end){
          lazy[node*2+1] += val;
          lazy[node*2+2] += val;
        }
        return;
    }
    int mid = (start+end)/2;
    update(node*2+1,start,mid,rangemin,rangemax,val);
    update(node*2+2,mid+1,end,rangemin,rangemax,val);
    seg[node] = seg[node*2+1]+seg[node*2+2];

}
int query(int node,int start,int end,int pos){
    if(lazy[node]!=0){
      seg[node] += lazy[node];
      if(start!=end){
        lazy[node*2+1] += lazy[node];
        lazy[node*2+2] += lazy[node];
      }
      lazy[node] = 0;
    }
    if(start==end&&start==pos){
      return seg[node];
    }
    int mid = (start+end)/2;
    if(pos<=mid){
      return query(node*2+1,start,mid,pos);
    }
    else{
      return query(node*2+2,mid+1,end,pos);
    }
}
int32_t main() {
  ios::sync_with_stdio(0);
  int no_of_input,no_of_query,up,down;
  int input,input1,input2,input3;
  cin >> no_of_input >> no_of_query >> up >> down;
  for(int i=0;i<=no_of_input;i++){
    cin >> input;
    vect1.push_back(input);
  }
  int cntup = 0;
  int cntdown = 0;
  for(int i=1;i<vect1.size();i++){
    if(vect1[i]>vect1[i-1]){
      cntup += abs(vect1[i]-vect1[i-1]);
    }
    else{
      cntdown += abs(vect1[i]-vect1[i-1]);
    }
  }
  build(0,0,vect1.size()-1);
  //cout << cntup << ' ' << cntdown << "\n";
  for(int i=0;i<no_of_query;i++){
    cin >> input1 >> input2 >> input3;
    //input1--,input2--;
    if(input1!=0){
      int before = query(0,0,vect1.size()-1,input1-1);
      int curr = query(0,0,vect1.size()-1,input1);
      if(curr>before){
        cntup -= abs(curr-before);
      }
      else{
        cntdown -= abs(curr-before);
      }
      curr += input3;
      if(curr>before){
        cntup += abs(curr-before);
      }
      else{
        cntdown += abs(curr-before);
      }
    }
    //cout << cntup << " " << cntdown << "---\n";
    if(input2!=vect1.size()-1){
      int next = query(0,0,vect1.size()-1,input2+1);
      int curr = query(0,0,vect1.size()-1,input2);
      if(next>curr){
        cntup -= abs(next-curr);
      }
      else{
        cntdown -= abs(next-curr);
      }
      curr += input3;
      if(next>curr){
        cntup += abs(next-curr);
      }
      else{
        cntdown += abs(next-curr);
      }
    }
    //cout << cntup << " " << cntdown << "--\n";
    update(0,0,vect1.size()-1,input1,input2,input3);
    cout << cntdown*down-cntup*up << "\n";
  }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int32_t main()':
foehn_phenomena.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<vect1.size();i++){
               ~^~~~~~~~~~~~~
foehn_phenomena.cpp:104:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(input2!=vect1.size()-1){
        ~~~~~~^~~~~~~~~~~~~~~~

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