Submission #517086

#	Time	Username	Problem	Language	Result	Execution time	Memory
517086		alirezasamimi100	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	579 ms	524292 KiB

timeleap

/*#pragma GCC optimize("Ofast,unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
using point=complex<double>;
#define F first
#define S second
//#define X real()
//#define Y imag()
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define kill(x) cout << x << '\n';exit(0)
#define killshayan kill("done!")
#define killmashtali kill("Hello, World!")
const int N=3e5+10,LN=19,M=3e2+10,SQ=256,BS=737,inf=1e9;
const ll INF=1e18;
const double pi=acos(-1);
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,greater<pii>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
struct node{
    ll mt,lx,rx,mn;
    ll get(ll x){
        if(x<=mt) return mn;
        return x-mt+mn;
    }
    ll getx(ll x){
        return min(rx,max(lx,x));
    }
    node operator+(node k){
        node ans={lx<rx?min(mt,max(lx,k.mt)):mt,k.getx(lx),k.getx(rx),mn+k.get(lx)};
        return ans;
    }
} f[N*4];
ll n,q,a[N],b[N],c[N],d[N],ans[N],t[N];
vector<ll> qu[N];
void build(ll v, ll l, ll r){
    if(r-l==1){
        f[v].mt=f[v].rx=b[l];
        f[v].lx=a[l];
        f[v].mn=0;
        return;
    }
    ll m=(l+r)>>1;
    build(lc,l,m);
    build(rc,m,r);
    f[v]=f[lc]+f[rc];
}
void upd(ll v, ll l, ll r, ll p){
    if(r-l==1){
        f[v].mt=f[v].rx=b[l];
        f[v].lx=a[l];
        f[v].mn=0;
        return;
    }
    ll m=(l+r)>>1;
    if(p<m) upd(lc,l,m,p);
    else upd(rc,m,r,p);
    f[v]=f[lc]+f[rc];
}
node get(ll v, ll l, ll r, ll tl, ll tr){
    if(tl>=tr || l>=tr || tl>=r) return f[0];
    if(l>=tl && r<=tr) return f[v];
    ll m=(l+r)>>1;
    return get(lc,l,m,tl,tr)+get(rc,m,r,tl,tr);
}
int main(){
    fast_io;
    f[0]={INF,-INF,INF,0};
    cin >> n >> q;
    for(ll i=1; i<n; i++){
        cin >> c[i] >> d[i];
        a[i]=c[i]-i;
        d[i]--;
        b[i]=d[i]-i;
    }
    build(1,1,n);
    for(ll i=1; i<=q; i++){
        cin >> t[i];
        if(t[i]==1){
            ll j,l,r;
            cin >> j >> l >> r;
            r--;
            qu[i]={j,l,r};
            a[j]=l-j;
            b[j]=r-j;
            upd(1,1,n,j);
        }else{
            ll s,st,e,et;
            cin >> s >> st >> e >> et;
            qu[i]={s,st,e,et};
            if(s<=e){
                et-=e;
                st-=s;
                if(s==e) ans[i]=max(0ll,st-et);
                else{
                    node k=get(1,1,n,s,e);
                    ans[i]=k.get(st)+max(0ll,k.getx(st)-et);
                }
            }
        }
    }
    for(ll i=1; i<n; i++){
        a[i]=c[n-i]-i;
        b[i]=d[n-i]-i;
    }
    for(ll i=1; i<=q; i++){
        if(t[i]==1){
            qu[i][0]=n-qu[i][0];
        }else{
            qu[i][0]=n+1-qu[i][0];
            qu[i][2]=n+1-qu[i][2];
        }
    }
    build(1,1,n);
    for(ll i=1; i<=q; i++){
        if(t[i]==1){
            ll j=qu[i][0],l=qu[i][1],r=qu[i][2];
            a[j]=l-j;
            b[j]=r-j;
            upd(1,1,n,j);
        }else{
            ll s=qu[i][0],st=qu[i][1],e=qu[i][2],et=qu[i][3];
            if(s<e){
                et-=e;
                st-=s;
                node k=get(1,1,n,s,e);
                ans[i]=k.get(st)+max(0ll,k.getx(st)-et);
            }
        }
    }
    for(ll i=1; i<=q; i++) if(t[i]==2) cout << ans[i] << '\n';
    return 0;
}

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