oj.uz

답안 #976398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
976398 2024-05-06T14:05:27 Z 8pete8 새 집 (APIO18_new_home) C++17
100 / 100
 4778 ms 495604 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
//#define double long double
const int mxn=1e6,inf=1e9,minf=-1e9,Mxn=1e8+1;
int mx;
bitset<Mxn>del;
set<int>pos[mxn+10];
int cnt=0;
int curid=0;
vector<int>comp;
int n,k,q;
priority_queue<pii,vector<pii>,greater<pii>>huh;
struct seg{
    priority_queue<pii>v[2*mxn+10];
    priority_queue<pii>v2[2*mxn+10];
    //v=-val v2=+val
    //keep max
    //val id
    void update(int l,int r,pii val,int type){//lazy on top, 1=right
        //cout<<l<<" "<<r<<'\n';
        //if(r<l)assert(0);
        l=max(l,0);
        r=max(r,l);
        //cout<<l<<" "<<r<<" "<<val.f<<"PPP\n";
        for(l+=mx,r+=mx;l<=r;l>>=1,r>>=1){
            if(l&1){
                if(type)v[l].push(val);
                else v2[l].push(val);
                l++;
            }
            if(!(r&1)){
                if(type)v[r].push(val);
                else v2[r].push(val);
                r--;
            }
        }
    }
    pii qry(int pos){
        int g=comp.size()-1;
        pos=min(pos,g);
        pii ans={minf,minf};
        for(pos+=mx;pos>=0;pos>>=1){
            while(!v[pos].empty()&&del[v[pos].top().s])v[pos].pop();
            if(v[pos].size())ans.f=max(ans.f,v[pos].top().f);
            while(!v2[pos].empty()&&del[v2[pos].top().s])v2[pos].pop();
            if(v2[pos].size())ans.s=max(ans.s,v2[pos].top().f);
            if(pos==0)break;
        }
        return ans;
    }
}seg;
int rangeleft[mxn+10],rangeright[mxn+10];
int rangeidleft[mxn+10],rangeidright[mxn+10];
int idpos[mxn+10],idposincomp[mxn+10];
int tmp;
void add(int x,int t){
    //cout<<"PPP\n";
    //x =pos in comp;
    auto it=pos[t].insert(x).f;
    if(it!=pos[t].begin()){
        it--;
        tmp=(*it);
        int val=ceil((idpos[tmp]+idpos[x])*1.0/2);
        //find mid point
        auto it2=lb(all(comp),val)-comp.begin();
        if(it2==comp.size())assert(0);
        //find mid point in comp
        if(it2<=idposincomp[tmp])it2=idposincomp[tmp]+1;
        rangeright[tmp]=it2-1;
        if(it2>idposincomp[x])rangeleft[x]=idposincomp[x];
        else rangeleft[x]=it2;
        del[rangeidright[tmp]]=1;
        rangeidright[tmp]=++curid;
        rangeidleft[x]=++curid;
        seg.update(idposincomp[tmp],rangeright[tmp],{-idpos[tmp],rangeidright[tmp]},1);
        it++;
    }
    else{
        rangeleft[x]=0;
        rangeidleft[x]=++curid;
    }
    it++;
    if(it!=pos[t].end()){
        tmp=(*it);
        int val=ceil((idpos[tmp]+idpos[x])*1.0/2);
        auto it2=lb(all(comp),val)-comp.begin();
        if(it2==comp.size())assert(0);
        if(it2<=idposincomp[x])it2=idposincomp[x]+1;
        rangeright[x]=it2-1;
        rangeleft[tmp]=it2;
        if(it2>idposincomp[tmp])rangeleft[tmp]=idposincomp[tmp];
        else rangeleft[tmp]=it2;
        del[rangeidleft[tmp]]=1;
        rangeidright[x]=++curid;
        rangeidleft[tmp]=++curid;
        seg.update(rangeleft[tmp],idposincomp[tmp],{idpos[tmp],rangeidleft[tmp]},0);
    }
    else{
        rangeright[x]=mx;
        rangeidright[x]=++curid;
    }
   // cout<<"LL\n";
    seg.update(rangeleft[x],idposincomp[x],{idpos[x],rangeidleft[x]},0);
    seg.update(idposincomp[x],rangeright[x],{-idpos[x],rangeidright[x]},1);
}
void die(int x,int t){
    del[rangeidleft[x]]=1;
    del[rangeidright[x]]=1;
    auto it=pos[t].find(x);
    if(it==pos[t].end())assert(0);
    int l,r;
    if(it==pos[t].begin()){
        it++;
        if(it!=pos[t].end()){
            tmp=(*it);
           seg.update(0,rangeleft[tmp]-1,{idpos[tmp],rangeidleft[tmp]},0);
           rangeleft[tmp]=0;
        }
        it--;
        pos[t].erase(it);
        return;
    }
    it--;
    l=(*it);
    it++;
    it++;
    if(it==pos[t].end()){
        if(rangeright[l]!=mx)seg.update(rangeright[l]+1,mx,{-idpos[l],rangeidright[l]},1);
        rangeright[l]=mx;
        it--;
        pos[t].erase(it);
        return;
    }
    else r=(*it);
    int val=ceil((idpos[l]+idpos[r])*1.0/2);
    auto it2=lb(all(comp),val)-comp.begin();
    if(it2==comp.size())assert(0);
    int k=it2;
    if(rangeright[l]>=it2)k=rangeright[l]+1;
    seg.update(rangeright[l],k-1,{-idpos[l],rangeidright[l]},1);
    if(rangeleft[r]<k)k=rangeleft[r];
    seg.update(k,rangeleft[r],{idpos[r],rangeidleft[r]},0);
    rangeright[l]=k-1;
    rangeleft[r]=k;
    it--;
    pos[t].erase(it);
    return;
}
int ans[mxn+10];
struct info{int time,etype,pos,type,id;};
bool cmp(info a,info b){
    if(a.pos==b.pos)return a.etype>b.etype;
    return a.pos<b.pos;
}
bool cmp2(info a,info b){
    if(a.time==b.time)return a.etype<b.etype;
    return a.time<b.time;
}
vector<info>event;
int what[mxn+10],bro[mxn+10],tt[mxn+10],ttt[mxn+10];
int32_t main(){
    fastio
    cin>>n>>k>>q;
    for(int i=0;i<n;i++){
        int x,t,a,b;cin>>x>>t>>a>>b;
        event.pb({a,1,x,t,i});
        event.pb({b+1,0,x,t,i});
        comp.pb(x);
    }
    vector<pair<pii,int>>qry(q);
    for(int i=0;i<q;i++)cin>>qry[i].f.s>>qry[i].f.f,qry[i].s=i,comp.pb(qry[i].f.s);
    sort(all(qry));
    sort(all(event),cmp);
    sort(all(comp));
    comp.erase(unique(all(comp)),comp.end());
    int cnt=0;
    for(auto &i:event){
        if(i.etype==0){
            i.id=what[i.id];
            continue;
        }
        what[i.id]=cnt;
        i.id=cnt;
        idpos[cnt]=i.pos;
        tt[cnt]=i.type;
        idposincomp[cnt]=lb(all(comp),i.pos)-comp.begin();
        ttt[cnt]=i.time;
        cnt++;
    }
    sort(all(event),cmp2);
    int p=cnt;
    mx=comp.size();
    int cur=0,g=0;
    cnt=0;
    for(int i=1;i<=k;i++)bro[i]=inf;
   // for(auto i:comp)cout<<i<<" ";
    //cout<<'\n';
    for(auto i:qry){
        g++;
        while(cur<event.size()&&event[cur].time<=i.f.f){
            //cout<<event[cur].pos<<" "<<event[cur].type<<" "<<event[cur].etype<<'\n';
            if(event[cur].etype){
                if(pos[event[cur].type].size()==0)cnt++;
                add(event[cur].id,event[cur].type);
            }
            else{
                die(event[cur].id,event[cur].type);
                if(pos[event[cur].type].size()==0)cnt--;
            }
            cur++;
            /*
            for(int ii=1;ii<=k;ii++){
                cout<<ii<<'\n';
                for(auto j:pos[ii]){
                    cout<<rangeidleft[j]<<" "<<idposincomp[j]<<" "<<rangeidright[j]<<"LL\n";
                }
            }

            cout<<"_____________\n";*/
        }
        pii bru=seg.qry(lb(all(comp),i.f.s)-comp.begin());
        if(cnt!=k)ans[i.s]=-1;
        else{
            /*
            for(int j=1;j<=p;j++){
                if(ttt[j]>3)continue;
                if(del[rangeidright[j]]!=del[rangeidleft[j]])assert(0);
                if(del[rangeidright[j]]&&del[rangeidleft[j]])continue;
                if((comp[rangeleft[j]]<=i.f.s&&i.f.s<=idpos[j])||(idpos[j]<=i.f.s&&i.f.s<=comp[rangeright[j]])){
                    int g=abs(i.f.s-idpos[j]);
                    bro[tt[j]]=min(bro[tt[j]],g);
                }
                //break;
            }*/
            ///for(int i=1;i<=k;i++)cout<<bro[i]<<'\n';
            //ans[i.s]=mx;
            if(bru.f!=minf)ans[i.s]=max(ans[i.s],i.f.s+bru.f);
            if(bru.s!=minf)ans[i.s]=max(ans[i.s],bru.s-i.f.s);
        }
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
	return 0;
}

/*
(2*n+q)log(n)*log(10^8)
when there are currently a,b,c shop active with the same k
int range of each shop will be (0,(a+b)/2),((a+b)/2+1,(b+c)/2),((b+c)/2+1,mx)
the contribution on range l,r when shop pos is x will be
x-a,x-b,x,c-x,d-x;
we can keep muliset segtree
*/

Compilation message

new_home.cpp: In function 'void add(int, int)':
new_home.cpp:101:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(it2==comp.size())assert(0);
      |            ~~~^~~~~~~~~~~~~
new_home.cpp:122:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         if(it2==comp.size())assert(0);
      |            ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'void die(int, int)':
new_home.cpp:172:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     if(it2==comp.size())assert(0);
      |        ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:235:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |         while(cur<event.size()&&event[cur].time<=i.f.f){
      |               ~~~^~~~~~~~~~~~~
new_home.cpp:226:9: warning: unused variable 'p' [-Wunused-variable]
  226 |     int p=cnt;
      |         ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 174916 KB Output is correct
2 Correct 41 ms 174932 KB Output is correct
3 Correct 41 ms 174928 KB Output is correct
4 Correct 47 ms 174796 KB Output is correct
5 Correct 42 ms 174992 KB Output is correct
6 Correct 43 ms 174928 KB Output is correct
7 Correct 42 ms 175036 KB Output is correct
8 Correct 41 ms 175040 KB Output is correct
9 Correct 41 ms 174932 KB Output is correct
10 Correct 42 ms 174912 KB Output is correct
11 Correct 42 ms 174936 KB Output is correct
12 Correct 42 ms 174932 KB Output is correct
13 Correct 46 ms 175052 KB Output is correct
14 Correct 42 ms 174940 KB Output is correct
15 Correct 41 ms 174940 KB Output is correct
16 Correct 42 ms 174936 KB Output is correct
17 Correct 47 ms 174936 KB Output is correct
18 Correct 42 ms 174928 KB Output is correct
19 Correct 42 ms 174936 KB Output is correct
20 Correct 47 ms 175140 KB Output is correct
21 Correct 43 ms 174940 KB Output is correct
22 Correct 42 ms 174932 KB Output is correct
23 Correct 41 ms 174900 KB Output is correct
24 Correct 42 ms 174928 KB Output is correct
25 Correct 43 ms 175040 KB Output is correct
26 Correct 42 ms 174932 KB Output is correct
27 Correct 43 ms 174932 KB Output is correct
28 Correct 41 ms 175116 KB Output is correct
29 Correct 42 ms 174936 KB Output is correct
30 Correct 41 ms 174928 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 174916 KB Output is correct
2 Correct 41 ms 174932 KB Output is correct
3 Correct 41 ms 174928 KB Output is correct
4 Correct 47 ms 174796 KB Output is correct
5 Correct 42 ms 174992 KB Output is correct
6 Correct 43 ms 174928 KB Output is correct
7 Correct 42 ms 175036 KB Output is correct
8 Correct 41 ms 175040 KB Output is correct
9 Correct 41 ms 174932 KB Output is correct
10 Correct 42 ms 174912 KB Output is correct
11 Correct 42 ms 174936 KB Output is correct
12 Correct 42 ms 174932 KB Output is correct
13 Correct 46 ms 175052 KB Output is correct
14 Correct 42 ms 174940 KB Output is correct
15 Correct 41 ms 174940 KB Output is correct
16 Correct 42 ms 174936 KB Output is correct
17 Correct 47 ms 174936 KB Output is correct
18 Correct 42 ms 174928 KB Output is correct
19 Correct 42 ms 174936 KB Output is correct
20 Correct 47 ms 175140 KB Output is correct
21 Correct 43 ms 174940 KB Output is correct
22 Correct 42 ms 174932 KB Output is correct
23 Correct 41 ms 174900 KB Output is correct
24 Correct 42 ms 174928 KB Output is correct
25 Correct 43 ms 175040 KB Output is correct
26 Correct 42 ms 174932 KB Output is correct
27 Correct 43 ms 174932 KB Output is correct
28 Correct 41 ms 175116 KB Output is correct
29 Correct 42 ms 174936 KB Output is correct
30 Correct 41 ms 174928 KB Output is correct
31 Correct 733 ms 222428 KB Output is correct
32 Correct 131 ms 186832 KB Output is correct
33 Correct 492 ms 205260 KB Output is correct
34 Correct 794 ms 222668 KB Output is correct
35 Correct 673 ms 216752 KB Output is correct
36 Correct 499 ms 205008 KB Output is correct
37 Correct 357 ms 207324 KB Output is correct
38 Correct 317 ms 200872 KB Output is correct
39 Correct 278 ms 202672 KB Output is correct
40 Correct 283 ms 200652 KB Output is correct
41 Correct 538 ms 209120 KB Output is correct
42 Correct 531 ms 210260 KB Output is correct
43 Correct 104 ms 188176 KB Output is correct
44 Correct 579 ms 207712 KB Output is correct
45 Correct 493 ms 205004 KB Output is correct
46 Correct 476 ms 201676 KB Output is correct
47 Correct 270 ms 205004 KB Output is correct
48 Correct 257 ms 205252 KB Output is correct
49 Correct 311 ms 207248 KB Output is correct
50 Correct 365 ms 212232 KB Output is correct
51 Correct 319 ms 206032 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2288 ms 391488 KB Output is correct
2 Correct 1386 ms 301980 KB Output is correct
3 Correct 1179 ms 353228 KB Output is correct
4 Correct 2141 ms 382176 KB Output is correct
5 Correct 1088 ms 272352 KB Output is correct
6 Correct 1358 ms 291148 KB Output is correct
7 Correct 1198 ms 350880 KB Output is correct
8 Correct 2103 ms 380980 KB Output is correct
9 Correct 2542 ms 396976 KB Output is correct
10 Correct 1878 ms 359916 KB Output is correct
11 Correct 1276 ms 314176 KB Output is correct
12 Correct 1647 ms 355580 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4503 ms 460740 KB Output is correct
2 Correct 568 ms 239044 KB Output is correct
3 Correct 2543 ms 333432 KB Output is correct
4 Correct 1532 ms 367480 KB Output is correct
5 Correct 3956 ms 453036 KB Output is correct
6 Correct 3264 ms 446964 KB Output is correct
7 Correct 2037 ms 307104 KB Output is correct
8 Correct 2327 ms 332276 KB Output is correct
9 Correct 1494 ms 381244 KB Output is correct
10 Correct 3645 ms 457820 KB Output is correct
11 Correct 4778 ms 495604 KB Output is correct
12 Correct 3580 ms 415344 KB Output is correct
13 Correct 1409 ms 347580 KB Output is correct
14 Correct 1358 ms 330988 KB Output is correct
15 Correct 1678 ms 363956 KB Output is correct
16 Correct 2290 ms 421232 KB Output is correct
17 Correct 1674 ms 343740 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 174916 KB Output is correct
2 Correct 41 ms 174932 KB Output is correct
3 Correct 41 ms 174928 KB Output is correct
4 Correct 47 ms 174796 KB Output is correct
5 Correct 42 ms 174992 KB Output is correct
6 Correct 43 ms 174928 KB Output is correct
7 Correct 42 ms 175036 KB Output is correct
8 Correct 41 ms 175040 KB Output is correct
9 Correct 41 ms 174932 KB Output is correct
10 Correct 42 ms 174912 KB Output is correct
11 Correct 42 ms 174936 KB Output is correct
12 Correct 42 ms 174932 KB Output is correct
13 Correct 46 ms 175052 KB Output is correct
14 Correct 42 ms 174940 KB Output is correct
15 Correct 41 ms 174940 KB Output is correct
16 Correct 42 ms 174936 KB Output is correct
17 Correct 47 ms 174936 KB Output is correct
18 Correct 42 ms 174928 KB Output is correct
19 Correct 42 ms 174936 KB Output is correct
20 Correct 47 ms 175140 KB Output is correct
21 Correct 43 ms 174940 KB Output is correct
22 Correct 42 ms 174932 KB Output is correct
23 Correct 41 ms 174900 KB Output is correct
24 Correct 42 ms 174928 KB Output is correct
25 Correct 43 ms 175040 KB Output is correct
26 Correct 42 ms 174932 KB Output is correct
27 Correct 43 ms 174932 KB Output is correct
28 Correct 41 ms 175116 KB Output is correct
29 Correct 42 ms 174936 KB Output is correct
30 Correct 41 ms 174928 KB Output is correct
31 Correct 733 ms 222428 KB Output is correct
32 Correct 131 ms 186832 KB Output is correct
33 Correct 492 ms 205260 KB Output is correct
34 Correct 794 ms 222668 KB Output is correct
35 Correct 673 ms 216752 KB Output is correct
36 Correct 499 ms 205008 KB Output is correct
37 Correct 357 ms 207324 KB Output is correct
38 Correct 317 ms 200872 KB Output is correct
39 Correct 278 ms 202672 KB Output is correct
40 Correct 283 ms 200652 KB Output is correct
41 Correct 538 ms 209120 KB Output is correct
42 Correct 531 ms 210260 KB Output is correct
43 Correct 104 ms 188176 KB Output is correct
44 Correct 579 ms 207712 KB Output is correct
45 Correct 493 ms 205004 KB Output is correct
46 Correct 476 ms 201676 KB Output is correct
47 Correct 270 ms 205004 KB Output is correct
48 Correct 257 ms 205252 KB Output is correct
49 Correct 311 ms 207248 KB Output is correct
50 Correct 365 ms 212232 KB Output is correct
51 Correct 319 ms 206032 KB Output is correct
52 Correct 338 ms 229888 KB Output is correct
53 Correct 304 ms 226420 KB Output is correct
54 Correct 536 ms 244500 KB Output is correct
55 Correct 446 ms 232652 KB Output is correct
56 Correct 404 ms 232132 KB Output is correct
57 Correct 531 ms 232544 KB Output is correct
58 Correct 453 ms 231908 KB Output is correct
59 Correct 451 ms 232144 KB Output is correct
60 Correct 530 ms 233480 KB Output is correct
61 Correct 92 ms 210520 KB Output is correct
62 Correct 311 ms 229296 KB Output is correct
63 Correct 490 ms 239016 KB Output is correct
64 Correct 523 ms 241664 KB Output is correct
65 Correct 566 ms 243844 KB Output is correct
66 Correct 560 ms 233824 KB Output is correct
67 Correct 151 ms 214080 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 174916 KB Output is correct
2 Correct 41 ms 174932 KB Output is correct
3 Correct 41 ms 174928 KB Output is correct
4 Correct 47 ms 174796 KB Output is correct
5 Correct 42 ms 174992 KB Output is correct
6 Correct 43 ms 174928 KB Output is correct
7 Correct 42 ms 175036 KB Output is correct
8 Correct 41 ms 175040 KB Output is correct
9 Correct 41 ms 174932 KB Output is correct
10 Correct 42 ms 174912 KB Output is correct
11 Correct 42 ms 174936 KB Output is correct
12 Correct 42 ms 174932 KB Output is correct
13 Correct 46 ms 175052 KB Output is correct
14 Correct 42 ms 174940 KB Output is correct
15 Correct 41 ms 174940 KB Output is correct
16 Correct 42 ms 174936 KB Output is correct
17 Correct 47 ms 174936 KB Output is correct
18 Correct 42 ms 174928 KB Output is correct
19 Correct 42 ms 174936 KB Output is correct
20 Correct 47 ms 175140 KB Output is correct
21 Correct 43 ms 174940 KB Output is correct
22 Correct 42 ms 174932 KB Output is correct
23 Correct 41 ms 174900 KB Output is correct
24 Correct 42 ms 174928 KB Output is correct
25 Correct 43 ms 175040 KB Output is correct
26 Correct 42 ms 174932 KB Output is correct
27 Correct 43 ms 174932 KB Output is correct
28 Correct 41 ms 175116 KB Output is correct
29 Correct 42 ms 174936 KB Output is correct
30 Correct 41 ms 174928 KB Output is correct
31 Correct 733 ms 222428 KB Output is correct
32 Correct 131 ms 186832 KB Output is correct
33 Correct 492 ms 205260 KB Output is correct
34 Correct 794 ms 222668 KB Output is correct
35 Correct 673 ms 216752 KB Output is correct
36 Correct 499 ms 205008 KB Output is correct
37 Correct 357 ms 207324 KB Output is correct
38 Correct 317 ms 200872 KB Output is correct
39 Correct 278 ms 202672 KB Output is correct
40 Correct 283 ms 200652 KB Output is correct
41 Correct 538 ms 209120 KB Output is correct
42 Correct 531 ms 210260 KB Output is correct
43 Correct 104 ms 188176 KB Output is correct
44 Correct 579 ms 207712 KB Output is correct
45 Correct 493 ms 205004 KB Output is correct
46 Correct 476 ms 201676 KB Output is correct
47 Correct 270 ms 205004 KB Output is correct
48 Correct 257 ms 205252 KB Output is correct
49 Correct 311 ms 207248 KB Output is correct
50 Correct 365 ms 212232 KB Output is correct
51 Correct 319 ms 206032 KB Output is correct
52 Correct 2288 ms 391488 KB Output is correct
53 Correct 1386 ms 301980 KB Output is correct
54 Correct 1179 ms 353228 KB Output is correct
55 Correct 2141 ms 382176 KB Output is correct
56 Correct 1088 ms 272352 KB Output is correct
57 Correct 1358 ms 291148 KB Output is correct
58 Correct 1198 ms 350880 KB Output is correct
59 Correct 2103 ms 380980 KB Output is correct
60 Correct 2542 ms 396976 KB Output is correct
61 Correct 1878 ms 359916 KB Output is correct
62 Correct 1276 ms 314176 KB Output is correct
63 Correct 1647 ms 355580 KB Output is correct
64 Correct 4503 ms 460740 KB Output is correct
65 Correct 568 ms 239044 KB Output is correct
66 Correct 2543 ms 333432 KB Output is correct
67 Correct 1532 ms 367480 KB Output is correct
68 Correct 3956 ms 453036 KB Output is correct
69 Correct 3264 ms 446964 KB Output is correct
70 Correct 2037 ms 307104 KB Output is correct
71 Correct 2327 ms 332276 KB Output is correct
72 Correct 1494 ms 381244 KB Output is correct
73 Correct 3645 ms 457820 KB Output is correct
74 Correct 4778 ms 495604 KB Output is correct
75 Correct 3580 ms 415344 KB Output is correct
76 Correct 1409 ms 347580 KB Output is correct
77 Correct 1358 ms 330988 KB Output is correct
78 Correct 1678 ms 363956 KB Output is correct
79 Correct 2290 ms 421232 KB Output is correct
80 Correct 1674 ms 343740 KB Output is correct
81 Correct 338 ms 229888 KB Output is correct
82 Correct 304 ms 226420 KB Output is correct
83 Correct 536 ms 244500 KB Output is correct
84 Correct 446 ms 232652 KB Output is correct
85 Correct 404 ms 232132 KB Output is correct
86 Correct 531 ms 232544 KB Output is correct
87 Correct 453 ms 231908 KB Output is correct
88 Correct 451 ms 232144 KB Output is correct
89 Correct 530 ms 233480 KB Output is correct
90 Correct 92 ms 210520 KB Output is correct
91 Correct 311 ms 229296 KB Output is correct
92 Correct 490 ms 239016 KB Output is correct
93 Correct 523 ms 241664 KB Output is correct
94 Correct 566 ms 243844 KB Output is correct
95 Correct 560 ms 233824 KB Output is correct
96 Correct 151 ms 214080 KB Output is correct
97 Correct 2019 ms 397668 KB Output is correct
98 Correct 569 ms 253108 KB Output is correct
99 Correct 3531 ms 348596 KB Output is correct
100 Correct 1758 ms 358600 KB Output is correct
101 Correct 3774 ms 456664 KB Output is correct
102 Correct 3459 ms 349268 KB Output is correct
103 Correct 2842 ms 359768 KB Output is correct
104 Correct 2156 ms 325140 KB Output is correct
105 Correct 1489 ms 334884 KB Output is correct
106 Correct 1393 ms 327616 KB Output is correct
107 Correct 3180 ms 416060 KB Output is correct
108 Correct 2846 ms 409356 KB Output is correct
109 Correct 3775 ms 384728 KB Output is correct
110 Correct 3354 ms 402648 KB Output is correct
111 Correct 2947 ms 418692 KB Output is correct
112 Correct 3772 ms 390948 KB Output is correct
113 Correct 324 ms 269280 KB Output is correct
114 Correct 2005 ms 404668 KB Output is correct
115 Correct 3060 ms 446352 KB Output is correct
116 Correct 3370 ms 466364 KB Output is correct
117 Correct 4003 ms 451864 KB Output is correct
118 Correct 4187 ms 406832 KB Output is correct
119 Correct 738 ms 279220 KB Output is correct
120 Correct 1259 ms 353204 KB Output is correct
121 Correct 1509 ms 370480 KB Output is correct
122 Correct 1439 ms 358500 KB Output is correct
123 Correct 1770 ms 363324 KB Output is correct
124 Correct 2079 ms 385840 KB Output is correct
125 Correct 1824 ms 357452 KB Output is correct
126 Correct 2114 ms 415748 KB Output is correct