oj.uz

Submission #865340

# Submission time Handle Problem Language Result Execution time Memory
865340 2023-10-24T07:34:34 Z guagua0407 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 254 ms 524288 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
    int s1,s2,e1,e2,sz;
    ll c1,c2;
};

const int mxn=2e3+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
int L[mxn],R[mxn];
node trash;
int cnt=0;

void merge(node &ans,node &a,node &b){
    if(a.sz==-1){
        ans=b;
        return;
    }
    if(b.sz==-1){
        ans=a;
        return;
    }
    ans.sz=a.sz+b.sz;
    ans.s1=a.s1;
    ans.s2=a.s2;
    {
        ans.c1=a.c1;
        if(a.e1>b.s1){
            ans.c1+=b.c1+(a.e1-b.s1);
            ans.e1=b.e1;
        }
        else if(a.e1>=b.s2){
            ll dif=b.c1-b.c2;
            ans.c1+=b.c2+max(0ll,dif-(b.s1-a.e1));
            int res=a.e1+b.sz;
            if(res>b.e1){
                ans.e1=b.e1;
            }
            else{
                ans.e1=max(res,b.e2);
            }
        }
        else{
            ans.c1+=b.c2;
            ans.e1=b.e2;
        }
    }
    {
        ans.c2=a.c2;
        if(a.e2>b.s1){
            ans.c2+=b.c1+(a.e2-b.s1);
            ans.e2=b.e1;
        }
        else if(a.e2>=b.s2){
            ll dif=b.c1-b.c2;
            ans.c2+=b.c2+max(0ll,dif-(b.s1-a.e2));
            int res=a.e2+b.sz;
            if(res>b.e1){
                ans.e2=b.e1;
            }
            else{
                ans.e2=max(res,b.e2);
            }
        }
        else{
            ans.c2+=b.c2;
            ans.e2=b.e2;
        }
    }
}

void build(int id,int l=1,int r=n-1,int v=1){
    if(l==r){
        segtree[id][v].s1=R[l]-1;
        segtree[id][v].s2=L[l];
        segtree[id][v].e1=R[l];
        segtree[id][v].e2=L[l]+1;
        segtree[id][v].c1=segtree[id][v].c2=0;
        segtree[id][v].sz=1;
        return;
    }
    int mid=(l+r)/2;
    build(id,l,mid,v*2);
    build(id,mid+1,r,v*2+1);
    merge(segtree[id][v],segtree[id][v*2],segtree[id][v*2+1]);
}

void update(int id,int pos,int s,int e,int l=1,int r=n-1,int v=1){
    if(l==r){
        segtree[id][v].s1=e-1;
        segtree[id][v].s2=s;
        segtree[id][v].e1=e;
        segtree[id][v].e2=s+1;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(id,pos,s,e,l,mid,v*2);
    else update(id,pos,s,e,mid+1,r,v*2+1);
    merge(segtree[id][v],segtree[id][v*2],segtree[id][v*2+1]);
}

node query(int id,int tl,int tr,int l=1,int r=n-1,int v=1){
    if(r<tl or tr<l){
        return trash;
    }
    if(tl<=l and r<=tr){
        return segtree[id][v];
    }
    int mid=(l+r)/2;
    node ans;
    node a=query(id,tl,min(mid,tr),l,mid,v*2);
    node b=query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
    merge(ans,a,b);
    return ans;
}

signed main() {_
    trash.sz=-1;
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>L[i]>>R[i];
    }
    build(0);
    reverse(L+1,L+n);
    reverse(R+1,R+n);
    build(1);
    reverse(L+1,L+n);
    reverse(R+1,R+n);
    for(int i=0;i<q;i++){
        int t;
        cin>>t;
        if(t==1){
            ll p,s,e;
            cin>>p>>s>>e;
            update(0,p,s,e);
            update(1,n-p,s,e);
        }
        else{
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            if(a==c){
                cout<<max(0,b-d)<<'\n';
                continue;
            }
            node tmp;
            if(a<c){
                tmp=query(0,a,c-1);
            }
            else{
                a=n-a+1;
                c=n-c+1;
                //swap(b,d);
                tmp=query(1,a,c-1);
            }
            /*cout<<tmp.sz<<'\n';
            cout<<tmp.s1<<' '<<tmp.s2<<'\n';
            cout<<tmp.e1<<' '<<tmp.e2<<'\n';
            cout<<tmp.c1<<' '<<tmp.c2<<'\n';*/
            ll ans=0;
            int fin;
            if(b>tmp.s1){
                ans+=tmp.c1+(b-tmp.s1);
                fin=tmp.e1;
            }
            else if(b>=tmp.s2){
                ll dif=tmp.c1-tmp.c2;
                ans+=tmp.c2+max(0ll,dif-(tmp.s1-b));
                int res=b+tmp.sz;
                if(res>tmp.e1){
                    fin=tmp.e1;
                }
                else{
                    fin=max(res,tmp.e2);
                }
            }
            else{
                ans+=tmp.c2;
                fin=tmp.e2;
            }
            cout<<ans+max(0,fin-d)<<'\n';;
        }
    }
    return 0;
}
//maybe its multiset not set

Compilation message

timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1368 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 2 ms 1372 KB Output is correct
18 Correct 2 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 2 ms 1368 KB Output is correct
22 Correct 2 ms 1368 KB Output is correct
23 Correct 2 ms 1372 KB Output is correct
24 Correct 2 ms 1140 KB Output is correct
25 Correct 2 ms 1372 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1368 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct
30 Correct 1 ms 1372 KB Output is correct
31 Correct 2 ms 1372 KB Output is correct
32 Correct 2 ms 1372 KB Output is correct
33 Correct 2 ms 1372 KB Output is correct
34 Correct 1 ms 1372 KB Output is correct
35 Correct 1 ms 1372 KB Output is correct
36 Correct 2 ms 1372 KB Output is correct
37 Correct 2 ms 1368 KB Output is correct
38 Correct 1 ms 1372 KB Output is correct
39 Correct 2 ms 1368 KB Output is correct
40 Correct 1 ms 1372 KB Output is correct
41 Runtime error 254 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1824 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1368 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 2 ms 1372 KB Output is correct
18 Correct 2 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 2 ms 1368 KB Output is correct
22 Correct 2 ms 1368 KB Output is correct
23 Correct 2 ms 1372 KB Output is correct
24 Correct 2 ms 1140 KB Output is correct
25 Correct 2 ms 1372 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1368 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct
30 Correct 1 ms 1372 KB Output is correct
31 Correct 2 ms 1372 KB Output is correct
32 Correct 2 ms 1372 KB Output is correct
33 Correct 2 ms 1372 KB Output is correct
34 Correct 1 ms 1372 KB Output is correct
35 Correct 1 ms 1372 KB Output is correct
36 Correct 2 ms 1372 KB Output is correct
37 Correct 2 ms 1368 KB Output is correct
38 Correct 1 ms 1372 KB Output is correct
39 Correct 2 ms 1368 KB Output is correct
40 Correct 1 ms 1372 KB Output is correct
41 Runtime error 254 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -