Submission #335783

#	Time	Username	Problem	Language	Result	Execution time	Memory
335783		tqbfjotld	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	981 ms	91116 KiB

timeleap

#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);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66