Submission #518931

#TimeUsernameProblemLanguageResultExecution timeMemory
518931Lam_lai_cuoc_doiFoehn Phenomena (JOI17_foehn_phenomena)C++17
30 / 100
395 ms16216 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template <class T> void read(T &x) { x = 0; register int c; while ((c = getchar()) && (c > '9' || c < '0')) ; for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; } constexpr bool typetest = 0; constexpr int N = 2e5 + 5; struct SegmentTree { int n; ll st[N * 4]; SegmentTree() { memset(st, 0, sizeof st); } void Push(int id) { if (st[id]) { st[id << 1] += st[id]; st[id << 1 | 1] += st[id]; st[id] = 0; } } void Build(int id, int l, int r, ll a[N]) { if (l == r) { st[id] = a[l]; return; } Build(id << 1, l, (l + r) / 2, a); Build(id << 1 | 1, (l + r) / 2 + 1, r, a); } void Build(ll a[N]) { Build(1, 1, n, a); } void Update(int id, int l, int r, const int &a, const int &b, const ll &v) { if (l > b || r < a) return; if (l >= a && r <= b) { st[id] += v; return; } Push(id); Update(id << 1, l, (l + r) / 2, a, b, v); Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v); } void Update(int l, int r, ll v) { Update(1, 1, n, l, r, v); } int Get(int x) { int l = 1, r = n, id = 1; while (1) { if (l == r) break; Push(id); if ((l + r) / 2 >= x) { id = id << 1; r = (l + r) / 2; } else { id = id << 1 | 1; l = (l + r) / 2 + 1; } } return st[id]; } } f; int n, q; ll s, t, a[N], ans; void Read() { cin >> n >> q >> s >> t; for (int i = 0; i <= n; ++i) cin >> a[i]; } void Remove(int l, int r) { if (r > n) return; ll u = l == 0 ? 0 : f.Get(l), v = f.Get(r); if (u < v) ans += (v - u) * s; else ans -= (u - v) * t; } void Add(int l, int r) { if (r > n) return; ll u = l == 0 ? 0 : f.Get(l), v = f.Get(r); // cerr << l << " " << r << ": " << u << " " << v << "\n"; if (u < v) ans -= (v - u) * s; else ans += (u - v) * t; } void Solve() { f.n = n; f.Build(a); for (int i = 1; i <= n; ++i) { Add(i - 1, i); // cout << i << ": " << ans << "\n"; } while (q--) { int l, r, x; cin >> l >> r >> x; Remove(l - 1, l); Remove(r, r + 1); f.Update(l, r, x); Add(l - 1, l); Add(r, r + 1); cout << ans << '\n'; } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("tests.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } int t(1); if (typetest) cin >> t; for (int _ = 1; _ <= t; ++_) { // cout << "Case " << _ << ": "; Read(); Solve(); } cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; } /* */

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void read(T&)':
foehn_phenomena.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
foehn_phenomena.cpp: In function 'int32_t main()':
foehn_phenomena.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...