제출 #587142

#제출 시각아이디문제언어결과실행 시간메모리
587142TheEvilBirdFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
454 ms38244 KiB
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <numeric> #include <string> #include <bitset> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <random> #include <ctime> #include <chrono> using namespace std; #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)((x).size()) typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; //typedef __int128_t int128; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const char en = '\n'; const int INF = 1e9 + 7; const ll INFLL = 1e18; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); #ifdef __APPLE__ #include "debug.h" //#define debug(...) 42 #else #define debug(...) 42 #endif ll s, t; struct SegTree { struct Node { ll T, l, r, pushed; }; int n, qL, qR, index; ll val, ans; const ll off = 0; vector<Node> tree; vector<ll> a; SegTree(int _n) { n = _n; tree.assign(4 * n, {0, 0, 0, off}); } void update_vertex(int v, int l, int r) { int m = (l + r) / 2, vL = 2 * v, vR = vL + 1; push(vL, l, m); push(vR, m, r); tree[v].T = tree[vL].T + tree[vR].T; if (tree[vL].r < tree[vR].l) { tree[v].T -= s * (tree[vR].l - tree[vL].r); } else if (tree[vL].r > tree[vR].l) { tree[v].T += t * (tree[vL].r - tree[vR].l); } tree[v].l = tree[vL].l; tree[v].r = tree[vR].r; } void push(int v, int l, int r) { if (tree[v].pushed == off) return; int m = (l + r) / 2, vL = 2 * v, vR = vL + 1; tree[v].l += tree[v].pushed; tree[v].r += tree[v].pushed; if (l + 1 != r) { tree[vL].pushed += tree[v].pushed; tree[vR].pushed += tree[v].pushed; } tree[v].pushed = off; } void build(vector<ll> &_a) { a = _a; build_tree(1, 0, n); } void build_tree(int v, int l, int r) { if (l + 1 == r) { tree[v] = {0, a[l], a[l], off}; return; } int m = (l + r) / 2, vL = 2 * v, vR = vL + 1; build_tree(vL, l, m); build_tree(vR, m, r); update_vertex(v, l, r); } void update_segment(int _qL, int _qR, ll _val) { qL = _qL; qR = _qR + 1; val = _val; update_segment_tree(1, 0, n); } void update_segment_tree(int v, int l, int r) { push(v, l, r); if (qL <= l && r <= qR) { tree[v].pushed += val; push(v, l, r); return; } int m = (l + r) / 2, vL = 2 * v, vR = vL + 1; if (qL < m) update_segment_tree(vL, l, m); if (m < qR) update_segment_tree(vR, m, r); update_vertex(v, l, r); } ll get_all() { return tree[1].T; } }; void solve() { int n, q; cin >> n >> q >> s >> t; vector<ll> a(n + 1); for (auto &i: a) cin >> i; SegTree tr(n + 1); tr.build(a); while (q--) { int l, r; ll x; cin >> l >> r >> x; tr.update_segment(l, r, x); cout << tr.get_all() << en; } } int main() { #ifdef __APPLE__ freopen("input.txt", "r", stdin); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

foehn_phenomena.cpp: In member function 'void SegTree::push(int, int, int)':
foehn_phenomena.cpp:84:13: warning: unused variable 'm' [-Wunused-variable]
   84 |         int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...