제출 #361971

#제출 시각아이디문제언어결과실행 시간메모리
361971GalebickosikasaFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
204 ms13164 KiB
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx") #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <unordered_map> #include <set> #include <map> #include <queue> #include <random> #include <chrono> #define fi first #define se second #define pb push_back #define ll long long #define ld long double #define hm unordered_map #define pii pair<int, int> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define cinv(v) for (auto& x: v) cin >> x #define fr(i, n) for (int i = 0; i < n; ++i) #define fl(i, l, n) for (int i = l; i < n; ++i) #define int ll template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;} template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;} using namespace std; #ifdef LOCAL #define dbg(x) cerr << #x << " : " << x << '\n' #else #define dbg(x) #endif //tg: @runningcherry template <typename T1, typename T2> ostream& operator << (ostream& out, const pair<T1, T2>& v) { out << v.fi << ", " << v.se; return out; } template<typename T> ostream& operator << (ostream& out, const vector<T>& v) { for (auto& x: v) out << x << " "; return out; } template <typename T1, typename T2> ostream& operator << (ostream& out, const map<T1, T2>& v) { for (auto& x: v) out << x << '\n'; return out; } template<typename T> ostream& operator << (ostream& out, const set<T>& v) { for (auto& x: v) out << x << " "; return out; } template<typename T> ostream& operator << (ostream& out, const multiset<T>& v) { for (auto& x: v) out << x << " "; return out; } template <typename T1, typename T2> istream& operator >> (istream& in, pair<T1, T2>& a) { in >> a.fi >> a.se; return in; } const ll inf = (ll) 2e9; const ld pi = asin (1) * 2; const ld eps = 1e-8; const ll mod = (ll)1e9 + 7; const ll ns = 97; const int maxn = 2e5 + 20; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); struct fenw { vector<int> t; fenw (int n) { t = vector<int> (n); } inline void add (int i, int x) { for (; i < sz (t); i += i & -i) t[i] += x; } inline int get (int i) { int ans = 0; for (; i > 0; i -= i & -i) ans += t[i]; return ans; } }; signed main () { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, q, s, t; cin >> n >> q >> s >> t; vector<int> goo (n + 1); cinv (goo); fenw fen (n + 10); int res = 0; fl (i, 1, n + 1) { fen.add (i, goo[i] - goo[i - 1]); if (goo[i - 1] < goo[i]) { res -= s * (goo[i] - goo[i - 1]); } else { res += t * (goo[i - 1] - goo[i]); } } dbg (res); while (q--) { int l, r, x; cin >> l >> r >> x; int a = fen.get (l - 1); int b = fen.get (l); if (a < b) res += s * (b - a); else res -= t * (a - b); if (r != n) { a = fen.get (r); b = fen.get (r + 1); if (a < b) res += s * (b - a); else res -= t * (a - b); } fen.add (l, x); fen.add (r + 1, -x); a = fen.get (l - 1); b = fen.get (l); if (a < b) res -= s * (b - a); else res += t * (a - b); if (r != n) { a = fen.get (r); b = fen.get (r + 1); if (a < b) res -= s * (b - a); else res += t * (a - b); } cout << res << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...