Submission #439047

#TimeUsernameProblemLanguageResultExecution timeMemory
439047LptN21Sjeckanje (COCI21_sjeckanje)C++14
0 / 110
10 ms12748 KiB
#include <bits/stdc++.h> using namespace std; #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); #define FF first #define SS second #define pb push_back #define sz(x) (int)x.size() //#define oo 2e18 #define eps 1e-9 #define PI acos(-1.0) #define lb lower_bound #define ub upper_bound #define all(a) (a).begin(), (a).end() typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> ii; typedef pair<int, ii> i3; const int N = 2e5+7, M=448; const int MOD = 1e9+7; const int oo=1e9+1; int n, m, k, t; struct Node{ ll ans; int l, r; Node() {ans=l=r=0;} Node(int v) {l=r=v, ans=abs(v);} bool sameType(int a, int b) { if((a<0&&b>0)||(a>0&&b<0)) return 0; return 1; } Node operator+(const Node &a) { Node b; b.l=l, b.r=a.r, b.ans=ans+a.ans; if(!sameType(r, a.l)) b.ans-=min(abs(r), abs(a.l)); return b; } } st[N<<2]; void update(int idx, int l0, int r0, int p, int v) { if(l0>p||r0<p) return; if(l0==r0&&l0==p) { st[idx].l+=v, st[idx].r+=v, st[idx].ans=abs(st[idx].l); return; } int mid=(l0+r0)/2; update(idx*2, l0, mid, p, v), update(idx*2+1, mid+1, r0, p, v); st[idx]=st[idx*2]+st[idx*2+1]; } Node get(int idx, int l0, int r0, int l, int r) { if(l0>r||r0<l) return Node(0); if(l<=l0&&r0<=r) return st[idx]; int mid=(l0+r0)/2; return get(idx*2, l0, mid, l, r)+get(idx*2+1, mid+1, r0, l, r); } void upd(int p, int v) {update(1, 1, n, p, v);} ll qry() {return get(1, 1, n, 1, n).ans;} signed main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); //fastIO; scanf("%d%d", &n, &m); int x, y; for(int i=1;i<=n;i++) { scanf("%d", &y); if(i>1) upd(i, y-x); x=y; } for(int i=1;i<=m;i++) { scanf("%d%d%d", &x, &y, &k); if(x!=1) upd(x, k); if(y!=n) upd(y+1, -k); printf("%lld\n", qry()); } return 0; } /* stuff you should look for - int overflow, array bounds - special cases (n=1?) - do smth instead of do nothing and stay organized - WRITE STUFF DOWN - DONT JUST STICK ON ONE APPROACH */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d", &y);
      |         ~~~~~^~~~~~~~~~
Main.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d%d", &x, &y, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...