Submission #119141

#	Time	Username	Problem	Language	Result	Execution time	Memory
119141		songc	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	1027 ms	86416 KiB

timeleap

#include <bits/stdc++.h>
#define INF 1234567890123456ll
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, Q;

struct Node{
    LL lr, rl, ll, rr;

    Node operator+(const Node &r)const{
        Node ret;
        ret.lr = max(lr, r.lr);
        ret.lr = max(ret.lr, lr + r.lr);
        ret.lr = max(ret.lr, ll + r.rr);

        ret.rl = max(rl, r.rl);
        ret.rl = max(ret.rl, rl + r.rl);
        ret.rl = max(ret.rl, rr + r.ll);

        ret.ll = max(ll, r.ll);
        ret.ll = max(ret.ll, lr + r.ll);
        ret.ll = max(ret.ll, ll + r.rl);

        ret.rr = max(rr, r.rr);
        ret.rr = max(ret.rr, rr + r.lr);
        ret.rr = max(ret.rr, rl + r.rr);
        return ret;
    }
} T[1202020], rT[1202020];

void update(int id, int s, int e, int t, Node x){
    if (e < t || t < s) return;
    if (s == e){
        T[id] = x;
        return;
    }
    int mid = (s+e)/2;
    update(id*2, s, mid, t, x);
    update(id*2+1, mid+1, e, t, x);
    T[id] = T[id*2] + T[id*2+1];
}

Node query(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return (Node){-INF,-INF,-INF,-INF};
    if (ts <= s && e <= te) return T[id];
    int mid = (s+e)/2;
    return query(id*2, s, mid, ts, te) + query(id*2+1, mid+1, e, ts, te);
}

void rupdate(int id, int s, int e, int t, Node x){
    if (e < t || t < s) return;
    if (s == e){
        rT[id] = x;
        return;
    }
    int mid = (s+e)/2;
    rupdate(id*2, s, mid, t, x);
    rupdate(id*2+1, mid+1, e, t, x);
    rT[id] = rT[id*2] + rT[id*2+1];
}

Node rquery(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return (Node){-INF,-INF,-INF,-INF};
    if (ts <= s && e <= te) return rT[id];
    int mid = (s+e)/2;
    return rquery(id*2, s, mid, ts, te) + rquery(id*2+1, mid+1, e, ts, te);
}

int main(){
    LL a, b, c, d;
    scanf("%d %d", &N, &Q);
    for (int i=1; i<N; i++){
        scanf("%lld %lld", &a, &b);
        update(1, 1, N, i, (Node){-INF, -INF, a-i, -b+1+i});
        rupdate(1, 1, N, N-i, (Node){-INF, -INF, a-N+i, -b+1+N-i});
    }
    while (Q--){
        scanf("%lld", &a);
        if (a == 1){
            scanf("%lld %lld %lld", &a, &b, &c);
            update(1, 1, N, a, (Node){-INF, -INF, b-a, -c+1+a});
            rupdate(1, 1, N, N-a, (Node){-INF, -INF, b-N+a, -c+1+N-a});
        }
        else{
            scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
            if (a <= c){
                Node ret = query(1, 1, N, a, c-1);
                printf("%lld\n", max(((Node){-INF,-INF,b-a,-b+a}+ret+(Node){-INF,-INF,d-c,-d+c}).lr, 0ll));
            }
            else{
                Node ret = rquery(1, 1, N, N+1-a, N-c);
                printf("%lld\n", max(((Node){-INF,-INF,b-N-1+a,-b+N+1-a}+ret+(Node){-INF,-INF,d-N-1+c,-d+N+1-c}).lr, 0ll));
            }
        }
    }
    return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a);
         ~~~~~^~~~~~~~~~~~
timeleap.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld %lld", &a, &b, &c);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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