Submission #521308

#	Time	Username	Problem	Language	Result	Execution time	Memory
521308		cig32	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	605 ms	19772 KiB

foehn_phenomena

#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
struct node {
  int upd = 0;
  int ans = 0;
} st[4*MAXN];
void prop(int idx) {
  st[2*idx+1].upd += st[idx].upd;
  st[2*idx+2].upd += st[idx].upd;
  st[2*idx+1].ans += st[idx].upd;
  st[2*idx+2].ans += st[idx].upd;
  st[idx].upd = 0;
  st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
}
void u(int l, int r, int constl, int constr, int idx, int val) {
  if(l <= constl && constr <= r) {
    st[idx].upd += val;
    st[idx].ans += val;
    return;
  }
  int mid = (constl + constr) >> 1;
  prop(idx);
  if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
  else {
    u(l, r, constl, mid, 2*idx+1, val);
    u(l, r, mid+1, constr, 2*idx+2, val);
  }
  st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
}
int qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) {
    return st[idx].ans;
  }
  int mid = (constl + constr) >> 1;
  prop(idx);
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else {
    return qu(l, r, constl, mid, 2*idx+1);
    return qu(l, r, mid+1, constr, 2*idx+2);
  }
}

void update(int l, int r, int v) {
  u(l, r, 0, MAXN-1, 0, v);
}
int query(int i) {
  return qu(i, i, 0, MAXN-1, 0);
}
void solve(int tc) {
  int n, q, S, T;
  cin >> n >> q >> S >> T;
  S = -S;
  int cur = 0;
  int a[n+1];
  for(int i=0; i<=n; i++) {
    cin >> a[i];
    update(i, i, a[i]);
  }
  for(int i=1; i<=n; i++) {
    if(a[i-1] < a[i]) cur += S * (a[i] - a[i-1]);
    else cur += T * (a[i-1] - a[i]);
  }
  while(q--) {
    int l, r, x;
    cin >> l >> r >> x;
    int f = -1;
    if(query(l-1) < query(l)) cur += f * S * (query(l) - query(l-1));
    else cur += f * T * (query(l-1) - query(l));
    if(r < n && query(r) < query(r+1)) cur += f * S * (query(r+1) - query(r));
    else if(r < n) cur += f * T * (query(r) - query(r+1));
    update(l, r, x);
    f = 1;
    if(query(l-1) < query(l)) cur += f * S * (query(l) - query(l-1));
    else cur += f * T * (query(l-1) - query(l));
    if(r < n && query(r) < query(r+1)) cur += f * S * (query(r+1) - query(r));
    else if(r < n) cur += f * T * (query(r) - query(r+1));
    cout << cur << "\n";
  }
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

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