Submission #463583

#	Time	Username	Problem	Language	Result	Execution time	Memory
463583		Mounir	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	663 ms	16228 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define deb first
#define fin second
#define int long long
using namespace std;

const int N = (1 << 18);
int arbre[N * 2];
int T, S;

int getSum(int noeud){
      int sum = 0;
      for (; noeud > 0; noeud /= 2)
            sum += arbre[noeud];
      return sum;
}

void ajouter(int gauche, int droite, int delta){
      while (droite >= gauche){
            if (gauche%2 == 1)
                  arbre[gauche++] += delta;
            if (droite%2 == 0)
                  arbre[droite--] += delta;
            gauche /= 2;
            droite /= 2;
      }
}

int ecarts[N * 2];
void calcEcart(int ind){
      ecarts[N + ind] = getSum(N + ind + 1) - getSum(N + ind);
      if (ecarts[N + ind] < 0)
            ecarts[N + ind] *= -T;
      else
            ecarts[N + ind] *= -S;
      for (int noeud = (N + ind)/2; noeud > 0; noeud /= 2)
            ecarts[noeud] = ecarts[noeud * 2] + ecarts[noeud * 2 + 1];
}

signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);

      int nMonts, nReqs; cin >> nMonts >> nReqs >> S >> T;
      for (int iMont = 0; iMont <= nMonts; ++iMont){
            cin >> arbre[iMont + N];
            if (iMont > 0)
                  calcEcart(iMont - 1);
      }

      for (int iReq = 0; iReq < nReqs; ++iReq){
            int gauche, droite, delta;
            cin >> gauche >> droite >> delta;

            ajouter(N + gauche, N + droite, delta);
            calcEcart(gauche - 1);
            if (droite != nMonts)
                  calcEcart(droite);
            cout << ecarts[1] << endl;
      }
      return 0;
 
}

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