oj.uz

Submission #1088705

# Submission time Handle Problem Language Result Execution time Memory
1088705 2024-09-14T20:24:33 Z alexander707070 New Home (APIO18_new_home) C++14
100 / 100
 4783 ms 524508 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#define MAXN 5000007
using namespace std;

const int inf=1e9+7;

int n,k,q,x,t,l,r,ans[300007];

struct event{
    int x,type,tim,id;

    inline friend bool operator < (event fr,event sc){
        if(fr.tim!=sc.tim)return fr.tim<sc.tim;
        else return fr.type<sc.type;
    }
}s[MAXN];

multiset<int> stores[300007];

/*void solve(){

    tim++; ask.clear();
    for(event e:z){
        if((e.type==0 or e.type==2) and false){
            sp[e.id]=tim;
        }else if(e.type==1){
            ask.push_back(e);
        }
    }

    poss.clear(); st.clear(); ts.clear();
    for(int i=1;i<=k;i++){
        if(sp[i]==tim)poss.push_back(i);
        else{
            vector<int> w;
            for(int f:stores[i]){
                w.push_back(f);
            }

            if(w.empty()){
                st.push_back({0,inf});
                ts.push_back({inf,2*inf});
                break;
            }

            st.push_back({0,w[0]});
            for(int f=0;f<w.size()-1;f++){
                int pos=(w[f]+w[f+1])/2+(w[f]+w[f+1])%2;
                int val=(w[f+1]-w[f])/2;

                st.push_back({pos,pos+val});
                ts.push_back({pos-(w[f]+w[f+1])%2,val-(pos-(w[f]+w[f+1])%2)});
            }
            ts.push_back({inf,-w.back()});
        }
    }

    if(!st.empty()){
        sort(st.begin(),st.end());
        sort(ts.begin(),ts.end());
        sort(ask.begin(),ask.end(),cmp);

        int pt=0;
        while(!pq.empty())pq.pop();

        for(int i=0;i<ask.size();i++){
            while(pt<st.size() and st[pt].first<=ask[i].x){
                pq.push(st[pt].second);
                pt++;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()-ask[i].x);
        }

        pt=ts.size()-1;
        while(!pq.empty())pq.pop();

        for(int i=ask.size()-1;i>=0;i--){
            while(pt>=0 and ts[pt].first>=ask[i].x){
                pq.push(ts[pt].second);
                pt--;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()+ask[i].x);
        }
    }

    for(event e:z){
        if(e.type==0){
            stores[e.id].insert(e.x);
        }else if(e.type==2){
            stores[e.id].erase(stores[e.id].find(e.x));
        }else{
            for(int i:poss){
                ans[e.id]=max(ans[e.id],calc(e.x,i));
            }
        }
    }
}*/

struct node{
    int l,r;
    int val;
    int setid;
};

int num,pt,ft;
node tree[4*MAXN];
multiset<int> vals[MAXN];

void update(int v,int l,int r,int pos,int val,bool t){
    if(l==r){
        if(tree[v].setid==0){
            ft++; tree[v].setid=ft;
        }

        int id=tree[v].setid;

        if(t)vals[id].insert(val);
        else vals[id].erase(vals[id].find(val));

        if(!vals[id].empty())tree[v].val=*vals[id].rbegin();
        else tree[v].val=-inf;
    }else{
        int tt=(l+r)/2;

        if(tree[v].l==0){
            num++; tree[v].l=num;
            tree[num].val=-inf;
        }
        if(tree[v].r==0){
            num++; tree[v].r=num;
            tree[num].val=-inf;
        }

        if(pos<=tt)update(tree[v].l,l,tt,pos,val,t);
        else update(tree[v].r,tt+1,r,pos,val,t);

        tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr or v==0)return -inf;

    if(l==ll and r==rr){
        return tree[v].val;
    }else{
        int tt=(l+r)/2;
        return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
    }
}

void addline(int pos,int val){
    update(1,0,inf,pos,val,true);
}

void remline(int pos,int val){
    update(1,0,inf,pos,val,false);
}

int up(int s){
    if(s>=0)return s/2+s%2;
    else return s/2;
}

int down(int s){
    if(s>=0)return s/2;
    else return s/2+s%2;
}

void add(int x,int type,bool dir){
    stores[type].insert(x);
    auto it=stores[type].find(x);

    it--;
    int lpos=*it;
    it++; it++;
    int rpos=*it;

    if(!dir){
        remline(up(lpos+rpos),(rpos-lpos)/2+up(lpos+rpos));
        addline(up(lpos+x),(x-lpos)/2+up(lpos+x));
        addline(up(x+rpos),(rpos-x)/2+up(x+rpos));
    }else{
        remline(down(lpos+rpos),(rpos-lpos)/2-down(lpos+rpos));
        addline(down(lpos+x),(x-lpos)/2-down(lpos+x));
        addline(down(x+rpos),(rpos-x)/2-down(x+rpos));
    }
}

void rem(int x,int type,bool dir){
    auto it=stores[type].find(x);

    it--;
    int lpos=*it;
    it++; it++;
    int rpos=*it;

    if(!dir){
        addline(up(lpos+rpos),(rpos-lpos)/2+up(lpos+rpos));
        remline(up(lpos+x),(x-lpos)/2+up(lpos+x));
        remline(up(x+rpos),(rpos-x)/2+up(x+rpos));
    }else{
        addline(down(lpos+rpos),(rpos-lpos)/2-down(lpos+rpos));
        remline(down(lpos+x),(x-lpos)/2-down(lpos+x));
        remline(down(x+rpos),(rpos-x)/2-down(x+rpos));
    }

    stores[type].erase(stores[type].find(x));
}

int maxs(int l,int r){
    return getmax(1,0,inf,l,r);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k>>q;

    for(int i=1;i<=k;i++){
        stores[i].insert(0);
        stores[i].insert(inf);
    }

    for(int i=1;i<=n;i++){
        cin>>x>>t>>l>>r;
        x+=inf/2;

        pt++; s[pt]={x,0,l,t};
        pt++; s[pt]={x,2,r,t};
    }

    for(int i=1;i<=q;i++){
        cin>>x>>t;
        x+=inf/2;

        pt++; s[pt]={x,1,t,i};
    }

    sort(s+1,s+pt+1);

    num=1;
    for(int i=1;i<=k;i++)addline(up(0+inf),inf/2+up(0+inf));
    
    for(int i=1;i<=pt;i++){
        if(s[i].type==0){
            add(s[i].x,s[i].id,false);
        }else if(s[i].type==2){
            rem(s[i].x,s[i].id,false);
        }else{
            ans[s[i].id]=max(ans[s[i].id],maxs(0,s[i].x)-s[i].x);
        }
    }
    
    for(int i=1;i<=k;i++){
        remline(up(0+inf),inf/2+up(0+inf));
        addline(down(0+inf),inf/2-down(0+inf));
    }

    for(int i=1;i<=pt;i++){
        if(s[i].type==0){
            add(s[i].x,s[i].id,true);
        }else if(s[i].type==2){
            rem(s[i].x,s[i].id,true);
        }else{
            ans[s[i].id]=max(ans[s[i].id],maxs(s[i].x,inf)+s[i].x);
        }
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>200000000)cout<<"-1\n";
        else cout<<ans[i]<<"\n";
    }

    return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 249168 KB Output is correct
2 Correct 94 ms 249392 KB Output is correct
3 Correct 107 ms 249172 KB Output is correct
4 Correct 95 ms 249308 KB Output is correct
5 Correct 98 ms 249428 KB Output is correct
6 Correct 98 ms 249936 KB Output is correct
7 Correct 98 ms 249688 KB Output is correct
8 Correct 94 ms 249916 KB Output is correct
9 Correct 96 ms 249828 KB Output is correct
10 Correct 98 ms 250020 KB Output is correct
11 Correct 121 ms 249936 KB Output is correct
12 Correct 96 ms 249936 KB Output is correct
13 Correct 100 ms 249684 KB Output is correct
14 Correct 97 ms 249936 KB Output is correct
15 Correct 94 ms 249880 KB Output is correct
16 Correct 93 ms 249940 KB Output is correct
17 Correct 98 ms 250056 KB Output is correct
18 Correct 97 ms 249940 KB Output is correct
19 Correct 100 ms 250028 KB Output is correct
20 Correct 100 ms 250000 KB Output is correct
21 Correct 97 ms 249416 KB Output is correct
22 Correct 94 ms 249936 KB Output is correct
23 Correct 99 ms 250016 KB Output is correct
24 Correct 92 ms 249976 KB Output is correct
25 Correct 99 ms 250084 KB Output is correct
26 Correct 94 ms 249932 KB Output is correct
27 Correct 93 ms 249200 KB Output is correct
28 Correct 93 ms 249828 KB Output is correct
29 Correct 101 ms 249940 KB Output is correct
30 Correct 95 ms 249680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 249168 KB Output is correct
2 Correct 94 ms 249392 KB Output is correct
3 Correct 107 ms 249172 KB Output is correct
4 Correct 95 ms 249308 KB Output is correct
5 Correct 98 ms 249428 KB Output is correct
6 Correct 98 ms 249936 KB Output is correct
7 Correct 98 ms 249688 KB Output is correct
8 Correct 94 ms 249916 KB Output is correct
9 Correct 96 ms 249828 KB Output is correct
10 Correct 98 ms 250020 KB Output is correct
11 Correct 121 ms 249936 KB Output is correct
12 Correct 96 ms 249936 KB Output is correct
13 Correct 100 ms 249684 KB Output is correct
14 Correct 97 ms 249936 KB Output is correct
15 Correct 94 ms 249880 KB Output is correct
16 Correct 93 ms 249940 KB Output is correct
17 Correct 98 ms 250056 KB Output is correct
18 Correct 97 ms 249940 KB Output is correct
19 Correct 100 ms 250028 KB Output is correct
20 Correct 100 ms 250000 KB Output is correct
21 Correct 97 ms 249416 KB Output is correct
22 Correct 94 ms 249936 KB Output is correct
23 Correct 99 ms 250016 KB Output is correct
24 Correct 92 ms 249976 KB Output is correct
25 Correct 99 ms 250084 KB Output is correct
26 Correct 94 ms 249932 KB Output is correct
27 Correct 93 ms 249200 KB Output is correct
28 Correct 93 ms 249828 KB Output is correct
29 Correct 101 ms 249940 KB Output is correct
30 Correct 95 ms 249680 KB Output is correct
31 Correct 685 ms 314828 KB Output is correct
32 Correct 416 ms 255596 KB Output is correct
33 Correct 629 ms 309360 KB Output is correct
34 Correct 637 ms 310616 KB Output is correct
35 Correct 706 ms 314208 KB Output is correct
36 Correct 697 ms 313744 KB Output is correct
37 Correct 497 ms 308016 KB Output is correct
38 Correct 495 ms 307536 KB Output is correct
39 Correct 407 ms 307920 KB Output is correct
40 Correct 434 ms 307540 KB Output is correct
41 Correct 512 ms 315356 KB Output is correct
42 Correct 521 ms 315476 KB Output is correct
43 Correct 337 ms 260892 KB Output is correct
44 Correct 506 ms 315732 KB Output is correct
45 Correct 495 ms 315476 KB Output is correct
46 Correct 461 ms 315476 KB Output is correct
47 Correct 357 ms 309844 KB Output is correct
48 Correct 351 ms 310612 KB Output is correct
49 Correct 363 ms 313172 KB Output is correct
50 Correct 414 ms 313172 KB Output is correct
51 Correct 368 ms 313168 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3992 ms 507784 KB Output is correct
2 Correct 4550 ms 494884 KB Output is correct
3 Correct 2893 ms 501852 KB Output is correct
4 Correct 3964 ms 507368 KB Output is correct
5 Correct 3936 ms 484244 KB Output is correct
6 Correct 4250 ms 493264 KB Output is correct
7 Correct 2556 ms 501844 KB Output is correct
8 Correct 2828 ms 512624 KB Output is correct
9 Correct 2771 ms 512080 KB Output is correct
10 Correct 3120 ms 506848 KB Output is correct
11 Correct 2076 ms 500208 KB Output is correct
12 Correct 2225 ms 504724 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4783 ms 515764 KB Output is correct
2 Correct 2092 ms 297552 KB Output is correct
3 Correct 4712 ms 506452 KB Output is correct
4 Correct 3314 ms 499772 KB Output is correct
5 Correct 4679 ms 519452 KB Output is correct
6 Correct 4189 ms 516784 KB Output is correct
7 Correct 4480 ms 504372 KB Output is correct
8 Correct 4635 ms 506136 KB Output is correct
9 Correct 3189 ms 501036 KB Output is correct
10 Correct 3719 ms 507180 KB Output is correct
11 Correct 3943 ms 516176 KB Output is correct
12 Correct 4207 ms 503120 KB Output is correct
13 Correct 1921 ms 500100 KB Output is correct
14 Correct 1971 ms 495520 KB Output is correct
15 Correct 2211 ms 500060 KB Output is correct
16 Correct 2582 ms 506244 KB Output is correct
17 Correct 2476 ms 496932 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 249168 KB Output is correct
2 Correct 94 ms 249392 KB Output is correct
3 Correct 107 ms 249172 KB Output is correct
4 Correct 95 ms 249308 KB Output is correct
5 Correct 98 ms 249428 KB Output is correct
6 Correct 98 ms 249936 KB Output is correct
7 Correct 98 ms 249688 KB Output is correct
8 Correct 94 ms 249916 KB Output is correct
9 Correct 96 ms 249828 KB Output is correct
10 Correct 98 ms 250020 KB Output is correct
11 Correct 121 ms 249936 KB Output is correct
12 Correct 96 ms 249936 KB Output is correct
13 Correct 100 ms 249684 KB Output is correct
14 Correct 97 ms 249936 KB Output is correct
15 Correct 94 ms 249880 KB Output is correct
16 Correct 93 ms 249940 KB Output is correct
17 Correct 98 ms 250056 KB Output is correct
18 Correct 97 ms 249940 KB Output is correct
19 Correct 100 ms 250028 KB Output is correct
20 Correct 100 ms 250000 KB Output is correct
21 Correct 97 ms 249416 KB Output is correct
22 Correct 94 ms 249936 KB Output is correct
23 Correct 99 ms 250016 KB Output is correct
24 Correct 92 ms 249976 KB Output is correct
25 Correct 99 ms 250084 KB Output is correct
26 Correct 94 ms 249932 KB Output is correct
27 Correct 93 ms 249200 KB Output is correct
28 Correct 93 ms 249828 KB Output is correct
29 Correct 101 ms 249940 KB Output is correct
30 Correct 95 ms 249680 KB Output is correct
31 Correct 685 ms 314828 KB Output is correct
32 Correct 416 ms 255596 KB Output is correct
33 Correct 629 ms 309360 KB Output is correct
34 Correct 637 ms 310616 KB Output is correct
35 Correct 706 ms 314208 KB Output is correct
36 Correct 697 ms 313744 KB Output is correct
37 Correct 497 ms 308016 KB Output is correct
38 Correct 495 ms 307536 KB Output is correct
39 Correct 407 ms 307920 KB Output is correct
40 Correct 434 ms 307540 KB Output is correct
41 Correct 512 ms 315356 KB Output is correct
42 Correct 521 ms 315476 KB Output is correct
43 Correct 337 ms 260892 KB Output is correct
44 Correct 506 ms 315732 KB Output is correct
45 Correct 495 ms 315476 KB Output is correct
46 Correct 461 ms 315476 KB Output is correct
47 Correct 357 ms 309844 KB Output is correct
48 Correct 351 ms 310612 KB Output is correct
49 Correct 363 ms 313172 KB Output is correct
50 Correct 414 ms 313172 KB Output is correct
51 Correct 368 ms 313168 KB Output is correct
52 Correct 624 ms 308436 KB Output is correct
53 Correct 581 ms 304976 KB Output is correct
54 Correct 713 ms 313684 KB Output is correct
55 Correct 551 ms 313684 KB Output is correct
56 Correct 565 ms 311960 KB Output is correct
57 Correct 543 ms 315384 KB Output is correct
58 Correct 587 ms 313752 KB Output is correct
59 Correct 590 ms 312064 KB Output is correct
60 Correct 575 ms 315148 KB Output is correct
61 Correct 398 ms 269368 KB Output is correct
62 Correct 628 ms 308664 KB Output is correct
63 Correct 718 ms 314960 KB Output is correct
64 Correct 721 ms 316092 KB Output is correct
65 Correct 643 ms 315888 KB Output is correct
66 Correct 557 ms 315728 KB Output is correct
67 Correct 408 ms 255832 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 249168 KB Output is correct
2 Correct 94 ms 249392 KB Output is correct
3 Correct 107 ms 249172 KB Output is correct
4 Correct 95 ms 249308 KB Output is correct
5 Correct 98 ms 249428 KB Output is correct
6 Correct 98 ms 249936 KB Output is correct
7 Correct 98 ms 249688 KB Output is correct
8 Correct 94 ms 249916 KB Output is correct
9 Correct 96 ms 249828 KB Output is correct
10 Correct 98 ms 250020 KB Output is correct
11 Correct 121 ms 249936 KB Output is correct
12 Correct 96 ms 249936 KB Output is correct
13 Correct 100 ms 249684 KB Output is correct
14 Correct 97 ms 249936 KB Output is correct
15 Correct 94 ms 249880 KB Output is correct
16 Correct 93 ms 249940 KB Output is correct
17 Correct 98 ms 250056 KB Output is correct
18 Correct 97 ms 249940 KB Output is correct
19 Correct 100 ms 250028 KB Output is correct
20 Correct 100 ms 250000 KB Output is correct
21 Correct 97 ms 249416 KB Output is correct
22 Correct 94 ms 249936 KB Output is correct
23 Correct 99 ms 250016 KB Output is correct
24 Correct 92 ms 249976 KB Output is correct
25 Correct 99 ms 250084 KB Output is correct
26 Correct 94 ms 249932 KB Output is correct
27 Correct 93 ms 249200 KB Output is correct
28 Correct 93 ms 249828 KB Output is correct
29 Correct 101 ms 249940 KB Output is correct
30 Correct 95 ms 249680 KB Output is correct
31 Correct 685 ms 314828 KB Output is correct
32 Correct 416 ms 255596 KB Output is correct
33 Correct 629 ms 309360 KB Output is correct
34 Correct 637 ms 310616 KB Output is correct
35 Correct 706 ms 314208 KB Output is correct
36 Correct 697 ms 313744 KB Output is correct
37 Correct 497 ms 308016 KB Output is correct
38 Correct 495 ms 307536 KB Output is correct
39 Correct 407 ms 307920 KB Output is correct
40 Correct 434 ms 307540 KB Output is correct
41 Correct 512 ms 315356 KB Output is correct
42 Correct 521 ms 315476 KB Output is correct
43 Correct 337 ms 260892 KB Output is correct
44 Correct 506 ms 315732 KB Output is correct
45 Correct 495 ms 315476 KB Output is correct
46 Correct 461 ms 315476 KB Output is correct
47 Correct 357 ms 309844 KB Output is correct
48 Correct 351 ms 310612 KB Output is correct
49 Correct 363 ms 313172 KB Output is correct
50 Correct 414 ms 313172 KB Output is correct
51 Correct 368 ms 313168 KB Output is correct
52 Correct 3992 ms 507784 KB Output is correct
53 Correct 4550 ms 494884 KB Output is correct
54 Correct 2893 ms 501852 KB Output is correct
55 Correct 3964 ms 507368 KB Output is correct
56 Correct 3936 ms 484244 KB Output is correct
57 Correct 4250 ms 493264 KB Output is correct
58 Correct 2556 ms 501844 KB Output is correct
59 Correct 2828 ms 512624 KB Output is correct
60 Correct 2771 ms 512080 KB Output is correct
61 Correct 3120 ms 506848 KB Output is correct
62 Correct 2076 ms 500208 KB Output is correct
63 Correct 2225 ms 504724 KB Output is correct
64 Correct 4783 ms 515764 KB Output is correct
65 Correct 2092 ms 297552 KB Output is correct
66 Correct 4712 ms 506452 KB Output is correct
67 Correct 3314 ms 499772 KB Output is correct
68 Correct 4679 ms 519452 KB Output is correct
69 Correct 4189 ms 516784 KB Output is correct
70 Correct 4480 ms 504372 KB Output is correct
71 Correct 4635 ms 506136 KB Output is correct
72 Correct 3189 ms 501036 KB Output is correct
73 Correct 3719 ms 507180 KB Output is correct
74 Correct 3943 ms 516176 KB Output is correct
75 Correct 4207 ms 503120 KB Output is correct
76 Correct 1921 ms 500100 KB Output is correct
77 Correct 1971 ms 495520 KB Output is correct
78 Correct 2211 ms 500060 KB Output is correct
79 Correct 2582 ms 506244 KB Output is correct
80 Correct 2476 ms 496932 KB Output is correct
81 Correct 624 ms 308436 KB Output is correct
82 Correct 581 ms 304976 KB Output is correct
83 Correct 713 ms 313684 KB Output is correct
84 Correct 551 ms 313684 KB Output is correct
85 Correct 565 ms 311960 KB Output is correct
86 Correct 543 ms 315384 KB Output is correct
87 Correct 587 ms 313752 KB Output is correct
88 Correct 590 ms 312064 KB Output is correct
89 Correct 575 ms 315148 KB Output is correct
90 Correct 398 ms 269368 KB Output is correct
91 Correct 628 ms 308664 KB Output is correct
92 Correct 718 ms 314960 KB Output is correct
93 Correct 721 ms 316092 KB Output is correct
94 Correct 643 ms 315888 KB Output is correct
95 Correct 557 ms 315728 KB Output is correct
96 Correct 408 ms 255832 KB Output is correct
97 Correct 3223 ms 501728 KB Output is correct
98 Correct 2077 ms 281700 KB Output is correct
99 Correct 4289 ms 487508 KB Output is correct
100 Correct 3472 ms 484112 KB Output is correct
101 Correct 4395 ms 518736 KB Output is correct
102 Correct 4654 ms 508516 KB Output is correct
103 Correct 2667 ms 480220 KB Output is correct
104 Correct 2746 ms 478892 KB Output is correct
105 Correct 1993 ms 478288 KB Output is correct
106 Correct 2049 ms 477588 KB Output is correct
107 Correct 2944 ms 513296 KB Output is correct
108 Correct 3218 ms 508860 KB Output is correct
109 Correct 3048 ms 515924 KB Output is correct
110 Correct 3199 ms 512852 KB Output is correct
111 Correct 3341 ms 508240 KB Output is correct
112 Correct 3146 ms 515404 KB Output is correct
113 Correct 1900 ms 350292 KB Output is correct
114 Correct 3108 ms 502196 KB Output is correct
115 Correct 4201 ms 523152 KB Output is correct
116 Correct 4383 ms 524508 KB Output is correct
117 Correct 4428 ms 519180 KB Output is correct
118 Correct 3329 ms 515952 KB Output is correct
119 Correct 2116 ms 282492 KB Output is correct
120 Correct 1253 ms 478080 KB Output is correct
121 Correct 1351 ms 503376 KB Output is correct
122 Correct 1409 ms 501840 KB Output is correct
123 Correct 1527 ms 508348 KB Output is correct
124 Correct 1844 ms 511884 KB Output is correct
125 Correct 1690 ms 509528 KB Output is correct
126 Correct 1986 ms 507436 KB Output is correct