제출 #199198

#제출 시각아이디문제언어결과실행 시간메모리
199198xiaowuc1Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
198 ms11768 KiB
#include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <vector> using namespace std; // BEGIN NO SAD #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef vector<int> vi; // END NO SAD typedef long long ll; typedef pair<int, int> pii; const int RAGETREE_SZ = 1 << 18; ll bit[RAGETREE_SZ]; void upd(int idx, ll val) { idx += 2; while(idx < RAGETREE_SZ) { bit[idx] += val; idx += idx & -idx; } } ll qry(int idx) { idx += 2; ll ret = 0; while(idx) { ret += bit[idx]; idx -= idx & -idx; } return ret; } void solve() { int n, q; ll s, t; ll pos = 0; ll neg = 0; cin >> n >> q >> s >> t; { ll last = 0; for(int i = 0; i <= n; i++) { ll curr; cin >> curr; upd(i, curr - last); last = curr; } } for(int i = 1; i <= n; i++) { ll delta = qry(i) - qry(i-1); if(delta > 0) pos += delta; else neg -= delta; } while(q--) { int lhs, rhs, k; cin >> lhs >> rhs >> k; ll delta; delta = qry(lhs) - qry(lhs-1); if(delta > 0) pos -= delta; else neg += delta; if(rhs < n) { delta = qry(rhs+1) - qry(rhs); if(delta > 0) pos -= delta; else neg += delta; } upd(lhs, k); upd(rhs+1, -k); delta = qry(lhs) - qry(lhs-1); if(delta > 0) pos += delta; else neg -= delta; if(rhs < n) { delta = qry(rhs+1) - qry(rhs); if(delta > 0) pos += delta; else neg -= delta; } cout << t*neg - s*pos << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...