제출 #873936

#제출 시각아이디문제언어결과실행 시간메모리
873936kh0iSjeckanje (COCI21_sjeckanje)C++17
0 / 110
1 ms348 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } #define sgn(x) ((x > 0) - (x < 0)) const ll INF = 1e18; const int N = 2e5 + 3; int n, m; ll a[N]; struct ST{ struct Node{ ll dak[2][2]; }; vector<Node> st; void init(int _n){ n = _n; st.resize(4 * n + 6); } Node combine(Node &x, Node &y, int mid){ Node res; res.dak[0][0] = max({x.dak[0][1] + y.dak[0][0], x.dak[0][0] + y.dak[1][0], x.dak[0][0] + y.dak[0][0]}); res.dak[1][0] = max({x.dak[1][1] + y.dak[1][0], x.dak[1][0] + y.dak[1][0], x.dak[1][0] + y.dak[0][0]}); res.dak[0][1] = max({x.dak[0][1] + y.dak[0][1], x.dak[0][0] + y.dak[0][1], x.dak[0][0] + y.dak[1][1]}); res.dak[1][1] = max({x.dak[1][1] + y.dak[0][1], x.dak[1][0] + y.dak[1][1], x.dak[1][0] + y.dak[0][1]}); if(sgn(a[mid]) * sgn(a[mid + 1]) >= 0){ res.dak[0][0] = max(res.dak[0][0], x.dak[0][1] + y.dak[1][0]); res.dak[0][1] = max(res.dak[0][1], x.dak[0][1] + y.dak[1][1]); res.dak[1][0] = max(res.dak[1][0], x.dak[1][1] + y.dak[1][0]); res.dak[1][1] = max(res.dak[1][1], x.dak[1][1] + y.dak[1][1]); } return res; } void _build(int id, int l, int r){ if(l == r){ st[id].dak[0][1] = st[id].dak[1][0] = -INF; st[id].dak[1][1] = abs(a[l]); st[id].dak[0][0] = 0; return; } int mid = (l + r) / 2; _build(2 * id, l, mid); _build(2 * id + 1, mid + 1, r); st[id] = combine(st[2 * id], st[2 * id + 1], mid); } void _update(int id, int l, int r, int pos){ if(pos < l or pos > r) return; if(l == r){ st[id].dak[0][1] = st[id].dak[1][0] = -INF; st[id].dak[1][1] = abs(a[l]); st[id].dak[0][0] = 0; return; } int mid = (l + r) / 2; if(pos <= mid) _update(2 * id, l, mid, pos); else _update(2 * id + 1, mid + 1, r, pos); st[id] = combine(st[2 * id], st[2 * id + 1], mid); } void build(){ _build(1, 1, n); } void update(int pos){ if(pos < 1 or pos > n) return; _update(1, 1, n, pos); } ll query(){ return max({st[1].dak[0][0], st[1].dak[0][1], st[1].dak[1][0], st[1].dak[1][1]}); } } dak; void solve(){ cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i < n; ++i) a[i] = a[i] - a[i + 1]; n--; dak.init(n); dak.build(); while(m--){ int l, r; ll x; cin >> l >> r >> x; a[l - 1] -= x; a[r] += x; dak.update(l - 1); dak.update(r); cout << dak.query() << '\n'; } } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "troll" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

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

Main.cpp: In function 'int32_t main()':
Main.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...