Submission #335783

#TimeUsernameProblemLanguageResultExecution timeMemory
335783tqbfjotldBitaro, who Leaps through Time (JOI19_timeleap)C++14
100 / 100
981 ms91116 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct val{ int a,b,c,d; val(){} val(int _a, int _b, int _c, int _d){ a = _a; b = _b; c = _c; d = _d; } int func(int S, int E){ return max(max(0LL,S-a)+max(0LL,b-E)+d,d+max(0LL,S-E+c)); } }; val mer(val a, val b){ val c = val(0,0,0,0); c.d = a.func(0,b.a) + b.func(b.a,1100000000LL); c.a = 1100000000LL-(a.func(1100000000LL,b.a) + b.func(b.a,1100000000LL) - c.d); c.b = a.func(0,a.b) + b.func(a.b,0)-c.d; if (c.d>0) c.c = -99999999999999999LL; else c.c = a.c+b.c; return c; } int L[300005]; int R[300005]; struct node{ int s,e; val v,v2; node *l,*r; node (int _s, int _e){ s = _s; e = _e; if (s==e){ v = val(R[s]-1,L[s]+1,1,0); v2 = val(R[s]-1,L[s]+1,1,0); } else{ l = new node(s,(s+e)/2); r = new node((s+e)/2+1,e); v = mer(l->v,r->v); v2 = mer(r->v2,l->v2); } } void upd(int pos){ if (s==e){ v = val(R[s]-1,L[s]+1,1,0); v2 = val(R[s]-1,L[s]+1,1,0); } else{ if (pos<=(s+e)/2){ l->upd(pos); } else{ r->upd(pos); } v = mer(l->v,r->v); v2 = mer(r->v2,l->v2); } } val qu(int a, int b, bool rev){ if (a<=s && e<=b){ return rev?v2:v; } if (b<=(s+e)/2){ return l->qu(a,b,rev); } if (a>(s+e)/2){ return r->qu(a,b,rev); } return rev?mer(r->qu(a,b,rev),l->qu(a,b,rev)):mer(l->qu(a,b,rev),r->qu(a,b,rev)); } }*root; int32_t main(){ int n,q; scanf("%lld%lld",&n,&q); for (int x = 0; x<n-1; x++){ scanf("%lld%lld",&L[x],&R[x]); } root = new node(0,n-1); for (int x = 0; x<q; x++){ int t; scanf("%lld",&t); if (t==1){ int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); a--; L[a] = b; R[a] = c; root->upd(a); } else{ int a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); a--;c--; if (a==c){ printf("%lld\n",max(0LL,b-d)); } else{ printf("%lld\n",root->qu(min(a,c),max(a,c)-1,c<a).func(b,d)); } } } }

Compilation message (stderr)

timeleap.cpp: In function 'int32_t main()':
timeleap.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     scanf("%lld%lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%lld%lld",&L[x],&R[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
timeleap.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |             scanf("%lld%lld%lld",&a,&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |             scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...