제출 #419714

#제출 시각아이디문제언어결과실행 시간메모리
419714arayiFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
756 ms22300 KiB
//Arayi #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <queue> #include <stack> #include <algorithm> #include <math.h> #include <vector> #include <cstring> #include <ctime> #include <set> #include <bitset> #include <map> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <ctime> #include <climits> #include <cassert> #include <chrono> #include <random> #include <complex> #define fr first #define sc second #define MP make_pair #define ad push_back #define PB push_back #define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define lli long long int #define y1 arayikhalatyan #define j1 jigglypuff #define ld long double #define itn int #define pir pair<int, int> #define all(x) (x).begin(), (x).end() #define str string #define enl endl #define en endl #define cd complex<long double> #define vcd vector<cd> #define vii vector<int> #define vlli vector<lli> using namespace std; lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); } ld dist(ld x, ld y1, ld x2, ld y2) { return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2)); } lli S(lli a) { return (a * (a + 1LL)) / 2; } mt19937 rnd(363542); char vow[] = { 'a', 'e', 'i', 'o', 'u' }; int dx[] = { 0, -1, 0, 1, -1, -1, 1, 1, 0 }; int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1, 0 }; const int N = 1e6 + 30; const lli mod = 1e9 - 1; const ld pi = acos(-1); const int T = 550; lli bp(lli a, lli b = mod - 2LL) { lli ret = 1; while (b) { if (b & 1) ret *= a, ret %= mod; a *= a; a %= mod; b >>= 1; } return ret; } ostream& operator<<(ostream& c, pir a) { c << a.fr << " " << a.sc; return c; } template<class T> void maxi(T& a, T b) { a = max(a, b); } template <class T> void mini(T& a, T b) { a = min(a, b); } int n, q; lli s1, t1, a, b; lli t[4*N], flg[4*N]; void push(int nd) { flg[nd * 2] += flg[nd]; flg[nd * 2 + 1] += flg[nd]; t[nd] += flg[nd]; flg[nd] = 0; } void upd(int l, int r, int v, int nl = 0, int nr = n , int nd = 1) { push(nd); if(l > nr || r < nl) return; if(l == nl && r == nr) { flg[nd] += v; push(nd); return; } int mid = (nl + nr)/2; upd(l, min(mid, r), v, nl, mid, nd * 2); upd(max(mid + 1, l), r, v, mid + 1, nr, nd * 2 + 1); t[nd] = t[nd * 2] + t[nd* 2 + 1]; } lli qry(int q, int l = 0, int r = n, int nd = 1) { push(nd); if(l > q || r < q) return 0; if(l==r) return t[nd]; int mid = (l + r)/ 2; return qry(q, l, mid, nd*2) + qry(q, mid + 1, r, nd * 2 + 1); } int main() { fastio; cin >> n >> q >> s1 >> t1; int x; cin >> x; upd(0, 0, x); for (int i = 0; i < n; i++) { cin >> x; upd(i + 1, i + 1, x); int sm = qry(i); if(sm >= x) a += sm - x; else b += x - sm; } //cout << a*t1-b*s1 << endl; while(q--) { lli l, r, v; cin >> l >> r >> v; lli sm = qry(l - 1), s = qry(l); if(sm >= s) a -= sm - s; else b -= s - sm; upd(l, r, v); s += v; if(sm >= s) a += sm - s; else b += s - sm; if(r < n) { sm = qry(r) - v, s = qry(r + 1); //cout << sm << " "<< s << endl; if(sm >= s) a -= sm - s; else b -= s - sm; sm += v; if(sm >= s) a += sm - s; else b += s - sm; } cout << a*t1 - b*s1 << "\n"; } return 0; } /* 5 4 4 1 2 3 1 3 4 5 3 4 5 2 3 2 1 3 1 1 3 5 2 3 4 5 2 1 3 1 __ *(><)* \/ / ||/ --|| || /\ / \ / \ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...