oj.uz

답안 #160307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160307 2019-10-26T19:36:11 Z galen_colin Foehn Phenomena (JOI17_foehn_phenomena) C++14
100 / 100
 724 ms 18180 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
 
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < n; i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const ll mod = 1000000007;
 
ll madd(ll a, ll b) {
  return (a + b) % mod;
}
ll msub(ll a, ll b) {
  return (((a - b) % mod) + mod) % mod;
}
ll mmul(ll a, ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
ll mpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp % 2 == 1){
        res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}
ll minv(ll base) {
  return mpow(base, mod - 2);
}
ll mdiv(ll a, ll b) {
  return mmul(a, minv(b));
}
ll gcd(ll x, ll y) {
  if (x == 0) return y;
  if (y == 0) return x;
  return gcd(y, x % y);
}
 
bool prime[1000006]; 
void sieve(int n) { 
  f0r(i, n + 1) prime[i] = 1;
  for (int p = 2; p * p <= n; p++) { 
    if (prime[p] == true) { 
      for (int i = p * p; i <= n; i += p) 
        prime[i] = false; 
    } 
  } 
  prime[1] = prime[0] = 0;
} 

template <typename num_t> 
struct segtree {
  int n, depth;
  vector<num_t> tree, lazy;

  void init(int s, int* arr) {
    n = s;
    tree = vector<num_t>(4 * s, 0);
    lazy = vector<num_t>(4 * s, 0);
    init(0, 0, n - 1, arr);
  }

  num_t init(int i, int l, int r, int* arr) {
    if (l == r) return tree[i] = arr[l];

    int mid = (l + r) / 2;
    num_t a = init(2 * i + 1, l, mid, arr),
          b = init(2 * i + 2, mid + 1, r, arr);
    return tree[i] = a.op(b);
  }

  void update(int l, int r, num_t v) {
	if (l > r) return;
    update(0, 0, n - 1, l, r, v);
  }

  num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
    eval_lazy(i, tl, tr);

    if (ql <= tl && tr <= qr) {
      lazy[i] = lazy[i].val + v.val;
      eval_lazy(i, tl, tr);
      return tree[i];
    }
    if (tl > tr || tr < ql || qr < tl) return tree[i];
    if (tl == tr) return tree[i];

    int mid = (tl + tr) / 2;
    num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
          b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
    return tree[i] = a.op(b);
  }

  num_t query(int l, int r) {
	if (l > r) return num_t::null_v;
    return query(0, 0, n-1, l, r);
  }

  num_t query(int i, int tl, int tr, int ql, int qr) {
    eval_lazy(i, tl, tr);
    
    if (ql <= tl && tr <= qr) return tree[i];
    if (tl > tr || tr < ql || qr < tl) return num_t::null_v;

    int mid = (tl + tr) / 2;
    num_t a = query(2 * i + 1, tl, mid, ql, qr),
          b = query(2 * i + 2, mid + 1, tr, ql, qr);
    return a.op(b);
  }

  void eval_lazy(int i, int l, int r) {
    tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
    if (l != r) {
      lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
      lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
    }

    lazy[i] = num_t();
  }
};

struct max_t {
  long long val;
  static const long long null_v = -9223372036854775807LL;

  max_t(): val(0) {}
  max_t(long long v): val(v) {}

  max_t op(max_t& other) {
    return max_t(max(val, other.val));
  }
  
  max_t lazy_op(max_t v, int size) {
    return max_t(val + v.val);
  }
};

ll n, m, k, q, Q, T, l, r, x, y, z;
int a[500005];
int b[500005];
string s, t;
ll ans = 0;

segtree<max_t> st;

int main() {
  io;
  // freopen("case", "r", stdin);
  // freopen("test.txt", "r", stdin);
  // freopen("case", "w", stdout);

  // usaco("file");

  cin >> n >> q >> x >> y;
  n++;
  ai(a, n);
  f0r(i, n - 1) {
    if (a[i] < a[i + 1]) ans -= x * (a[i + 1] - a[i]);
    else ans -= y * (a[i + 1] - a[i]);
  }
  st.init(n, a);
  f0r(i, q) {
    cin >> l >> r >> z;
    ll leftl = st.query(l - 1, l - 1).val, leftr = st.query(l, l).val;

    if (leftl < leftr) ans += x * (leftr - leftl);
    else ans += y * (leftr - leftl);
    leftr += z;
    if (leftl < leftr) ans -= x * (leftr - leftl);
    else ans -= y * (leftr - leftl);

    if (r != n - 1) {
      ll rightl = st.query(r, r).val, rightr = st.query(r + 1, r + 1).val;
      if (rightl < rightr) ans += x * (rightr - rightl);
      else ans += y * (rightr - rightl);
      rightl += z;
      if (rightl < rightr) ans -= x * (rightr - rightl);
      else ans -= y * (rightr - rightl);
    }

    st.update(l, r, z);
    cout << ans << '\n';
  }
}

Compilation message

foehn_phenomena.cpp: In function 'void usaco(std::__cxx11::string)':
foehn_phenomena.cpp:54:53: note: #pragma message: be careful, freopen may be wrong
   #pragma message("be careful, freopen may be wrong")
                                                     ^
foehn_phenomena.cpp:55:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:56:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 564 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 4 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 654 ms 16924 KB Output is correct
2 Correct 686 ms 16584 KB Output is correct
3 Correct 713 ms 17016 KB Output is correct
4 Correct 679 ms 16120 KB Output is correct
5 Correct 724 ms 17108 KB Output is correct
6 Correct 414 ms 17520 KB Output is correct
7 Correct 404 ms 17272 KB Output is correct
8 Correct 537 ms 17364 KB Output is correct
9 Correct 531 ms 17848 KB Output is correct
10 Correct 567 ms 16376 KB Output is correct
11 Correct 497 ms 17400 KB Output is correct
12 Correct 419 ms 17872 KB Output is correct
13 Correct 415 ms 18040 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 564 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 4 ms 504 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 654 ms 16924 KB Output is correct
23 Correct 686 ms 16584 KB Output is correct
24 Correct 713 ms 17016 KB Output is correct
25 Correct 679 ms 16120 KB Output is correct
26 Correct 724 ms 17108 KB Output is correct
27 Correct 414 ms 17520 KB Output is correct
28 Correct 404 ms 17272 KB Output is correct
29 Correct 537 ms 17364 KB Output is correct
30 Correct 531 ms 17848 KB Output is correct
31 Correct 567 ms 16376 KB Output is correct
32 Correct 497 ms 17400 KB Output is correct
33 Correct 419 ms 17872 KB Output is correct
34 Correct 415 ms 18040 KB Output is correct
35 Correct 697 ms 15928 KB Output is correct
36 Correct 698 ms 17400 KB Output is correct
37 Correct 724 ms 18168 KB Output is correct
38 Correct 685 ms 18180 KB Output is correct
39 Correct 679 ms 18040 KB Output is correct
40 Correct 642 ms 18168 KB Output is correct
41 Correct 693 ms 17844 KB Output is correct
42 Correct 648 ms 18040 KB Output is correct
43 Correct 640 ms 17144 KB Output is correct
44 Correct 646 ms 17656 KB Output is correct
45 Correct 647 ms 17500 KB Output is correct
46 Correct 679 ms 18140 KB Output is correct
47 Correct 409 ms 17956 KB Output is correct
48 Correct 417 ms 18168 KB Output is correct
49 Correct 673 ms 17020 KB Output is correct
50 Correct 489 ms 17820 KB Output is correct
51 Correct 405 ms 17888 KB Output is correct
52 Correct 646 ms 17912 KB Output is correct