oj.uz

Submission #568456

# Submission time Handle Problem Language Result Execution time Memory
568456 2022-05-25T13:27:02 Z Ahmadsm2005 Interval Collection (CCO20_day2problem2) C++17
22 / 25
 7000 ms 336156 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int N,L,R;
pair<int,int>seg[1<<21],seg2[1<<21];
set<int>SEG[1<<20],SEG2[1<<20];
map<pair<int,int>,int>COUNT;
map<pair<int,int>,set<pair<int,int>>>MP;
multiset<pair<int,int>>GLOBAL; ///{R-L,L}
char C;
pair<int,int>G1(pair<int,int>A,pair<int,int>B){
if(A.first==INT_MAX)
return B;
else if(B.first==INT_MAX)
return A;
if(A.second<B.second)
return A;
else if(A.second==B.second&&A.first>B.first)
return A;
return B;
}
pair<int,int>G2(pair<int,int>A,pair<int,int>B){
if(A.first==INT_MAX)
return B;
else if(B.first==INT_MAX)
return A;
if(A.first>B.first)
return A;
else if(A.first==B.first&&A.second<B.second)
return A;
return B;
}
void updA1(int T,int v,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG[T].insert(v);
seg[idx]={T,*SEG[T].begin()};
return;
}
if((LL+RR)/2>=T)
updA1(T,v,LL,(LL+RR)/2,idx*2+1);
else
updA1(T,v,(LL+RR)/2+1,RR,idx*2+2);
seg[idx]=G1(seg[idx*2+1],seg[idx*2+2]);
}
void updR1(int T,int v,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG[T].erase(v);
if(SEG[T].size())
seg[idx]={T,*SEG[T].begin()};
else
seg[idx]={INT_MAX,INT_MAX};
return;
}
if((LL+RR)/2>=T)
updR1(T,v,LL,(LL+RR)/2,idx*2+1);
else
updR1(T,v,(LL+RR)/2+1,RR,idx*2+2);
seg[idx]=G1(seg[idx*2+1],seg[idx*2+2]);
}
pair<int,int>query1(int L,int R,int LL=0,int RR=(1<<20)-1,int idx=0){
if(LL>=L&&RR<=R)
return seg[idx];
else if(LL>R||RR<L)
return{INT_MAX,INT_MAX};
return G1(query1(L,R,LL,(LL+RR)/2,idx*2+1),query1(L,R,(LL+RR)/2+1,RR,idx*2+2));
}
pair<int,int>query2(int L,int R,int LL=0,int RR=(1<<20)-1,int idx=0){
if(LL>=L&&RR<=R)
return seg2[idx];
else if(LL>R||RR<L)
return{INT_MAX,INT_MAX};
return G2(query2(L,R,LL,(LL+RR)/2,idx*2+1),query2(L,R,(LL+RR)/2+1,RR,idx*2+2));
}
void updA2(int v,int T,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG2[T].insert(-v);
seg2[idx]={-(*SEG2[T].begin()),T};
return;
}
if((LL+RR)/2>=T)
updA2(v,T,LL,(LL+RR)/2,idx*2+1);
else
updA2(v,T,(LL+RR)/2+1,RR,idx*2+2);
seg2[idx]=G2(seg2[idx*2+1],seg2[idx*2+2]);
}
void updR2(int v,int T,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG2[T].erase(-v);
if(SEG2[T].size())
seg2[idx]={-(*SEG2[T].begin()),T};
else
seg2[idx]={INT_MAX,INT_MAX};
return;
}
if((LL+RR)/2>=T)
updR2(v,T,LL,(LL+RR)/2,idx*2+1);
else
updR2(v,T,(LL+RR)/2+1,RR,idx*2+2);
seg2[idx]=G2(seg2[idx*2+1],seg2[idx*2+2]);
}
int main()
{
cin.tie(0),ios_base::sync_with_stdio(0);
cin>>N;
for(int i=0;i<(1<<21);i++){
seg[i]={INT_MAX,INT_MAX};
seg2[i]={INT_MAX,INT_MAX};
}
while(N--){
cin>>C>>L>>R;
if(C=='A'){
COUNT[make_pair(L,R)]++;
if(COUNT[make_pair(L,R)]==1){
updA1(L,R);
updA2(L,R);
pair<int,int>F1=query1(0,(1<<20)-1);
pair<int,int>F2=query2(0,(1<<20)-1);
if(F1.second>F2.first){
cout<<F2.second-F1.first<<endl;
continue;
}
F1=query1(R,(1<<20)-1);
F2=query2(0,L);
if(F1.first!=INT_MAX){
GLOBAL.insert({F1.second-L,L});
MP[make_pair(L,R)].insert({F1.first,F1.second});
MP[make_pair(F1.first,F1.second)].insert({L,R});
}
if(F2.first!=INT_MAX){
GLOBAL.insert({R-F2.first,F2.first});
MP[make_pair(L,R)].insert({F2.first,F2.second});
MP[make_pair(F2.first,F2.second)].insert({L,R});
}
}
else{
pair<int,int>F1=query1(0,(1<<20)-1);
pair<int,int>F2=query2(0,(1<<20)-1);
if(F1.second>F2.first){
cout<<F2.second-F1.first<<endl;
continue;
}
}
cout<<(GLOBAL.begin()->first)<<endl;
}
else{
COUNT[make_pair(L,R)]--;
if(COUNT[make_pair(L,R)]==0){
updR1(L,R);
updR2(L,R);
for(auto itr=MP[make_pair(L,R)].begin();itr!=MP[make_pair(L,R)].end();itr++){
MP[*itr].erase({L,R});
int L1=(itr->first),R1=(itr->second);
pair<int,int>F1=query1(R1,(1<<20)-1);
pair<int,int>F2=query2(0,L1);
if(F1.first!=INT_MAX){
if(MP[make_pair(L1,R1)].find({F1.first,F1.second})==MP[make_pair(L1,R1)].end()){
GLOBAL.insert({F1.second-L1,L1});
MP[make_pair(L1,R1)].insert({F1.first,F1.second});
MP[make_pair(F1.first,F1.second)].insert({L1,R1});
}
}
if(F2.first!=INT_MAX){
if(MP[make_pair(L1,R1)].find({F2.first,F2.second})==MP[make_pair(L1,R1)].end()){
GLOBAL.insert({R1-F2.first,F2.first});
MP[make_pair(L1,R1)].insert({F2.first,F2.second});
MP[make_pair(F2.first,F2.second)].insert({L1,R1});
}
}
int LL=min(L,L1),RR=max(R,R1);
GLOBAL.erase(GLOBAL.lower_bound(make_pair(RR-LL,LL)));
}
MP[make_pair(L,R)].clear();
pair<int,int>FF1=query1(0,(1<<20)-1);
pair<int,int>FF2=query2(0,(1<<20)-1);
if(FF1.second>FF2.first){
if(GLOBAL.size())exit(1);
cout<<FF2.second-FF1.first<<endl;
continue;
}
}
else{
pair<int,int>FF1=query1(0,(1<<20)-1);
pair<int,int>FF2=query2(0,(1<<20)-1);
if(FF1.second>FF2.first){
if(GLOBAL.size())exit(1);
cout<<FF2.second-FF1.first<<endl;
continue;
}
}
cout<<(GLOBAL.begin()->first)<<endl;
}
}
}
/*
5
A 1 2
A 5 6
A 3 4
R 1 2
R 5 6
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 131732 KB Output is correct
2 Correct 65 ms 131636 KB Output is correct
3 Correct 67 ms 131660 KB Output is correct
4 Correct 64 ms 131640 KB Output is correct
5 Correct 66 ms 131708 KB Output is correct
6 Correct 65 ms 131612 KB Output is correct
7 Correct 65 ms 131600 KB Output is correct
8 Correct 65 ms 131660 KB Output is correct
9 Correct 65 ms 131704 KB Output is correct
10 Correct 64 ms 131716 KB Output is correct
11 Correct 65 ms 131776 KB Output is correct
12 Correct 65 ms 131660 KB Output is correct
13 Correct 65 ms 131872 KB Output is correct
14 Correct 66 ms 131760 KB Output is correct
15 Correct 64 ms 131812 KB Output is correct
16 Correct 67 ms 131764 KB Output is correct
17 Correct 66 ms 131672 KB Output is correct
18 Correct 64 ms 131620 KB Output is correct
19 Correct 64 ms 131588 KB Output is correct
20 Correct 64 ms 131588 KB Output is correct
21 Correct 65 ms 131656 KB Output is correct
22 Correct 65 ms 131820 KB Output is correct
23 Correct 65 ms 131600 KB Output is correct
24 Correct 70 ms 131660 KB Output is correct
25 Correct 66 ms 131808 KB Output is correct
26 Correct 64 ms 131772 KB Output is correct
27 Correct 66 ms 131744 KB Output is correct
28 Correct 64 ms 131788 KB Output is correct
29 Correct 70 ms 131856 KB Output is correct
30 Correct 66 ms 131832 KB Output is correct
31 Correct 67 ms 131748 KB Output is correct
32 Correct 66 ms 131736 KB Output is correct
33 Correct 63 ms 131780 KB Output is correct
34 Correct 64 ms 131616 KB Output is correct
35 Correct 64 ms 131660 KB Output is correct
36 Correct 65 ms 131620 KB Output is correct
37 Correct 65 ms 131684 KB Output is correct
38 Correct 64 ms 131624 KB Output is correct
39 Correct 65 ms 131676 KB Output is correct
40 Correct 67 ms 131640 KB Output is correct
41 Correct 67 ms 131788 KB Output is correct
42 Correct 64 ms 131572 KB Output is correct
43 Correct 64 ms 131572 KB Output is correct
44 Correct 64 ms 131676 KB Output is correct
45 Correct 65 ms 131636 KB Output is correct
46 Correct 63 ms 131624 KB Output is correct
47 Correct 63 ms 131600 KB Output is correct
48 Correct 66 ms 131644 KB Output is correct
49 Correct 64 ms 131632 KB Output is correct
50 Correct 64 ms 131704 KB Output is correct
51 Correct 64 ms 131620 KB Output is correct
52 Correct 64 ms 131632 KB Output is correct
53 Correct 65 ms 131624 KB Output is correct
54 Correct 69 ms 131664 KB Output is correct
55 Correct 65 ms 131696 KB Output is correct
56 Correct 65 ms 131748 KB Output is correct
57 Correct 64 ms 131720 KB Output is correct
58 Correct 65 ms 131660 KB Output is correct
59 Correct 66 ms 131736 KB Output is correct
60 Correct 66 ms 131956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 131732 KB Output is correct
2 Correct 65 ms 131636 KB Output is correct
3 Correct 67 ms 131660 KB Output is correct
4 Correct 64 ms 131640 KB Output is correct
5 Correct 66 ms 131708 KB Output is correct
6 Correct 65 ms 131612 KB Output is correct
7 Correct 65 ms 131600 KB Output is correct
8 Correct 65 ms 131660 KB Output is correct
9 Correct 65 ms 131704 KB Output is correct
10 Correct 64 ms 131716 KB Output is correct
11 Correct 65 ms 131776 KB Output is correct
12 Correct 65 ms 131660 KB Output is correct
13 Correct 65 ms 131872 KB Output is correct
14 Correct 66 ms 131760 KB Output is correct
15 Correct 64 ms 131812 KB Output is correct
16 Correct 67 ms 131764 KB Output is correct
17 Correct 66 ms 131672 KB Output is correct
18 Correct 64 ms 131620 KB Output is correct
19 Correct 64 ms 131588 KB Output is correct
20 Correct 64 ms 131588 KB Output is correct
21 Correct 65 ms 131656 KB Output is correct
22 Correct 65 ms 131820 KB Output is correct
23 Correct 65 ms 131600 KB Output is correct
24 Correct 70 ms 131660 KB Output is correct
25 Correct 66 ms 131808 KB Output is correct
26 Correct 64 ms 131772 KB Output is correct
27 Correct 66 ms 131744 KB Output is correct
28 Correct 64 ms 131788 KB Output is correct
29 Correct 70 ms 131856 KB Output is correct
30 Correct 66 ms 131832 KB Output is correct
31 Correct 67 ms 131748 KB Output is correct
32 Correct 66 ms 131736 KB Output is correct
33 Correct 63 ms 131780 KB Output is correct
34 Correct 64 ms 131616 KB Output is correct
35 Correct 64 ms 131660 KB Output is correct
36 Correct 65 ms 131620 KB Output is correct
37 Correct 65 ms 131684 KB Output is correct
38 Correct 64 ms 131624 KB Output is correct
39 Correct 65 ms 131676 KB Output is correct
40 Correct 67 ms 131640 KB Output is correct
41 Correct 67 ms 131788 KB Output is correct
42 Correct 64 ms 131572 KB Output is correct
43 Correct 64 ms 131572 KB Output is correct
44 Correct 64 ms 131676 KB Output is correct
45 Correct 65 ms 131636 KB Output is correct
46 Correct 63 ms 131624 KB Output is correct
47 Correct 63 ms 131600 KB Output is correct
48 Correct 66 ms 131644 KB Output is correct
49 Correct 64 ms 131632 KB Output is correct
50 Correct 64 ms 131704 KB Output is correct
51 Correct 64 ms 131620 KB Output is correct
52 Correct 64 ms 131632 KB Output is correct
53 Correct 65 ms 131624 KB Output is correct
54 Correct 69 ms 131664 KB Output is correct
55 Correct 65 ms 131696 KB Output is correct
56 Correct 65 ms 131748 KB Output is correct
57 Correct 64 ms 131720 KB Output is correct
58 Correct 65 ms 131660 KB Output is correct
59 Correct 66 ms 131736 KB Output is correct
60 Correct 66 ms 131956 KB Output is correct
61 Correct 63 ms 131516 KB Output is correct
62 Correct 63 ms 131612 KB Output is correct
63 Correct 64 ms 131540 KB Output is correct
64 Correct 130 ms 135392 KB Output is correct
65 Correct 131 ms 133324 KB Output is correct
66 Correct 117 ms 132852 KB Output is correct
67 Correct 92 ms 132756 KB Output is correct
68 Correct 132 ms 135420 KB Output is correct
69 Correct 131 ms 133336 KB Output is correct
70 Correct 120 ms 132856 KB Output is correct
71 Correct 106 ms 132860 KB Output is correct
72 Correct 125 ms 136904 KB Output is correct
73 Correct 129 ms 136140 KB Output is correct
74 Correct 137 ms 136120 KB Output is correct
75 Correct 129 ms 135904 KB Output is correct
76 Correct 125 ms 137756 KB Output is correct
77 Correct 128 ms 137840 KB Output is correct
78 Correct 123 ms 137804 KB Output is correct
79 Correct 135 ms 137848 KB Output is correct
80 Correct 143 ms 135444 KB Output is correct
81 Correct 128 ms 133324 KB Output is correct
82 Correct 121 ms 132888 KB Output is correct
83 Correct 84 ms 132736 KB Output is correct
84 Correct 131 ms 135416 KB Output is correct
85 Correct 132 ms 133304 KB Output is correct
86 Correct 119 ms 132848 KB Output is correct
87 Correct 110 ms 132872 KB Output is correct
88 Correct 129 ms 136916 KB Output is correct
89 Correct 143 ms 136148 KB Output is correct
90 Correct 127 ms 135872 KB Output is correct
91 Correct 139 ms 135964 KB Output is correct
92 Correct 132 ms 137860 KB Output is correct
93 Correct 122 ms 137852 KB Output is correct
94 Correct 120 ms 137724 KB Output is correct
95 Correct 126 ms 137884 KB Output is correct
96 Correct 85 ms 132788 KB Output is correct
97 Correct 83 ms 132792 KB Output is correct
98 Correct 83 ms 132788 KB Output is correct
99 Correct 83 ms 132764 KB Output is correct
100 Correct 108 ms 132852 KB Output is correct
101 Correct 117 ms 132812 KB Output is correct
102 Correct 106 ms 132916 KB Output is correct
103 Correct 83 ms 132828 KB Output is correct
104 Correct 132 ms 135372 KB Output is correct
105 Correct 126 ms 133228 KB Output is correct
106 Correct 106 ms 132840 KB Output is correct
107 Correct 87 ms 132812 KB Output is correct
108 Correct 140 ms 134900 KB Output is correct
109 Correct 128 ms 133256 KB Output is correct
110 Correct 109 ms 132916 KB Output is correct
111 Correct 85 ms 132836 KB Output is correct
112 Correct 88 ms 134132 KB Output is correct
113 Correct 99 ms 134468 KB Output is correct
114 Correct 88 ms 134100 KB Output is correct
115 Correct 95 ms 134348 KB Output is correct
116 Correct 90 ms 134220 KB Output is correct
117 Correct 96 ms 134520 KB Output is correct
118 Correct 86 ms 134144 KB Output is correct
119 Correct 93 ms 134396 KB Output is correct
120 Correct 88 ms 134200 KB Output is correct
121 Correct 94 ms 134476 KB Output is correct
122 Correct 107 ms 136456 KB Output is correct
123 Correct 99 ms 136520 KB Output is correct
124 Correct 119 ms 133148 KB Output is correct
125 Correct 110 ms 132432 KB Output is correct
126 Correct 111 ms 132364 KB Output is correct
127 Correct 120 ms 133552 KB Output is correct
128 Correct 107 ms 132416 KB Output is correct
129 Correct 104 ms 132256 KB Output is correct
130 Correct 121 ms 133748 KB Output is correct
131 Correct 108 ms 132484 KB Output is correct
132 Correct 106 ms 132296 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 131732 KB Output is correct
2 Correct 65 ms 131636 KB Output is correct
3 Correct 67 ms 131660 KB Output is correct
4 Correct 64 ms 131640 KB Output is correct
5 Correct 66 ms 131708 KB Output is correct
6 Correct 65 ms 131612 KB Output is correct
7 Correct 65 ms 131600 KB Output is correct
8 Correct 65 ms 131660 KB Output is correct
9 Correct 65 ms 131704 KB Output is correct
10 Correct 64 ms 131716 KB Output is correct
11 Correct 65 ms 131776 KB Output is correct
12 Correct 65 ms 131660 KB Output is correct
13 Correct 65 ms 131872 KB Output is correct
14 Correct 66 ms 131760 KB Output is correct
15 Correct 64 ms 131812 KB Output is correct
16 Correct 67 ms 131764 KB Output is correct
17 Correct 66 ms 131672 KB Output is correct
18 Correct 64 ms 131620 KB Output is correct
19 Correct 64 ms 131588 KB Output is correct
20 Correct 64 ms 131588 KB Output is correct
21 Correct 65 ms 131656 KB Output is correct
22 Correct 65 ms 131820 KB Output is correct
23 Correct 65 ms 131600 KB Output is correct
24 Correct 70 ms 131660 KB Output is correct
25 Correct 66 ms 131808 KB Output is correct
26 Correct 64 ms 131772 KB Output is correct
27 Correct 66 ms 131744 KB Output is correct
28 Correct 64 ms 131788 KB Output is correct
29 Correct 70 ms 131856 KB Output is correct
30 Correct 66 ms 131832 KB Output is correct
31 Correct 67 ms 131748 KB Output is correct
32 Correct 66 ms 131736 KB Output is correct
33 Correct 63 ms 131780 KB Output is correct
34 Correct 64 ms 131616 KB Output is correct
35 Correct 64 ms 131660 KB Output is correct
36 Correct 65 ms 131620 KB Output is correct
37 Correct 65 ms 131684 KB Output is correct
38 Correct 64 ms 131624 KB Output is correct
39 Correct 65 ms 131676 KB Output is correct
40 Correct 67 ms 131640 KB Output is correct
41 Correct 67 ms 131788 KB Output is correct
42 Correct 64 ms 131572 KB Output is correct
43 Correct 64 ms 131572 KB Output is correct
44 Correct 64 ms 131676 KB Output is correct
45 Correct 65 ms 131636 KB Output is correct
46 Correct 63 ms 131624 KB Output is correct
47 Correct 63 ms 131600 KB Output is correct
48 Correct 66 ms 131644 KB Output is correct
49 Correct 64 ms 131632 KB Output is correct
50 Correct 64 ms 131704 KB Output is correct
51 Correct 64 ms 131620 KB Output is correct
52 Correct 64 ms 131632 KB Output is correct
53 Correct 65 ms 131624 KB Output is correct
54 Correct 69 ms 131664 KB Output is correct
55 Correct 65 ms 131696 KB Output is correct
56 Correct 65 ms 131748 KB Output is correct
57 Correct 64 ms 131720 KB Output is correct
58 Correct 65 ms 131660 KB Output is correct
59 Correct 66 ms 131736 KB Output is correct
60 Correct 66 ms 131956 KB Output is correct
61 Correct 63 ms 131516 KB Output is correct
62 Correct 63 ms 131612 KB Output is correct
63 Correct 64 ms 131540 KB Output is correct
64 Correct 130 ms 135392 KB Output is correct
65 Correct 131 ms 133324 KB Output is correct
66 Correct 117 ms 132852 KB Output is correct
67 Correct 92 ms 132756 KB Output is correct
68 Correct 132 ms 135420 KB Output is correct
69 Correct 131 ms 133336 KB Output is correct
70 Correct 120 ms 132856 KB Output is correct
71 Correct 106 ms 132860 KB Output is correct
72 Correct 125 ms 136904 KB Output is correct
73 Correct 129 ms 136140 KB Output is correct
74 Correct 137 ms 136120 KB Output is correct
75 Correct 129 ms 135904 KB Output is correct
76 Correct 125 ms 137756 KB Output is correct
77 Correct 128 ms 137840 KB Output is correct
78 Correct 123 ms 137804 KB Output is correct
79 Correct 135 ms 137848 KB Output is correct
80 Correct 143 ms 135444 KB Output is correct
81 Correct 128 ms 133324 KB Output is correct
82 Correct 121 ms 132888 KB Output is correct
83 Correct 84 ms 132736 KB Output is correct
84 Correct 131 ms 135416 KB Output is correct
85 Correct 132 ms 133304 KB Output is correct
86 Correct 119 ms 132848 KB Output is correct
87 Correct 110 ms 132872 KB Output is correct
88 Correct 129 ms 136916 KB Output is correct
89 Correct 143 ms 136148 KB Output is correct
90 Correct 127 ms 135872 KB Output is correct
91 Correct 139 ms 135964 KB Output is correct
92 Correct 132 ms 137860 KB Output is correct
93 Correct 122 ms 137852 KB Output is correct
94 Correct 120 ms 137724 KB Output is correct
95 Correct 126 ms 137884 KB Output is correct
96 Correct 85 ms 132788 KB Output is correct
97 Correct 83 ms 132792 KB Output is correct
98 Correct 83 ms 132788 KB Output is correct
99 Correct 83 ms 132764 KB Output is correct
100 Correct 108 ms 132852 KB Output is correct
101 Correct 117 ms 132812 KB Output is correct
102 Correct 106 ms 132916 KB Output is correct
103 Correct 83 ms 132828 KB Output is correct
104 Correct 132 ms 135372 KB Output is correct
105 Correct 126 ms 133228 KB Output is correct
106 Correct 106 ms 132840 KB Output is correct
107 Correct 87 ms 132812 KB Output is correct
108 Correct 140 ms 134900 KB Output is correct
109 Correct 128 ms 133256 KB Output is correct
110 Correct 109 ms 132916 KB Output is correct
111 Correct 85 ms 132836 KB Output is correct
112 Correct 88 ms 134132 KB Output is correct
113 Correct 99 ms 134468 KB Output is correct
114 Correct 88 ms 134100 KB Output is correct
115 Correct 95 ms 134348 KB Output is correct
116 Correct 90 ms 134220 KB Output is correct
117 Correct 96 ms 134520 KB Output is correct
118 Correct 86 ms 134144 KB Output is correct
119 Correct 93 ms 134396 KB Output is correct
120 Correct 88 ms 134200 KB Output is correct
121 Correct 94 ms 134476 KB Output is correct
122 Correct 107 ms 136456 KB Output is correct
123 Correct 99 ms 136520 KB Output is correct
124 Correct 119 ms 133148 KB Output is correct
125 Correct 110 ms 132432 KB Output is correct
126 Correct 111 ms 132364 KB Output is correct
127 Correct 120 ms 133552 KB Output is correct
128 Correct 107 ms 132416 KB Output is correct
129 Correct 104 ms 132256 KB Output is correct
130 Correct 121 ms 133748 KB Output is correct
131 Correct 108 ms 132484 KB Output is correct
132 Correct 106 ms 132296 KB Output is correct
133 Correct 513 ms 147880 KB Output is correct
134 Correct 445 ms 138904 KB Output is correct
135 Correct 368 ms 136912 KB Output is correct
136 Correct 182 ms 136636 KB Output is correct
137 Correct 506 ms 148064 KB Output is correct
138 Correct 475 ms 139012 KB Output is correct
139 Correct 364 ms 136956 KB Output is correct
140 Correct 293 ms 136736 KB Output is correct
141 Correct 508 ms 154444 KB Output is correct
142 Correct 488 ms 151352 KB Output is correct
143 Correct 455 ms 150280 KB Output is correct
144 Correct 468 ms 150056 KB Output is correct
145 Correct 449 ms 158284 KB Output is correct
146 Correct 426 ms 158244 KB Output is correct
147 Correct 433 ms 158288 KB Output is correct
148 Correct 451 ms 158172 KB Output is correct
149 Correct 506 ms 147824 KB Output is correct
150 Correct 460 ms 138872 KB Output is correct
151 Correct 363 ms 136892 KB Output is correct
152 Correct 169 ms 136544 KB Output is correct
153 Correct 523 ms 147916 KB Output is correct
154 Correct 455 ms 138860 KB Output is correct
155 Correct 357 ms 136872 KB Output is correct
156 Correct 304 ms 136604 KB Output is correct
157 Correct 488 ms 154656 KB Output is correct
158 Correct 523 ms 150992 KB Output is correct
159 Correct 462 ms 150204 KB Output is correct
160 Correct 461 ms 150008 KB Output is correct
161 Correct 435 ms 158200 KB Output is correct
162 Correct 431 ms 158116 KB Output is correct
163 Correct 434 ms 157812 KB Output is correct
164 Correct 423 ms 158028 KB Output is correct
165 Correct 167 ms 136648 KB Output is correct
166 Correct 165 ms 136596 KB Output is correct
167 Correct 149 ms 136548 KB Output is correct
168 Correct 156 ms 136784 KB Output is correct
169 Correct 314 ms 136696 KB Output is correct
170 Correct 246 ms 136744 KB Output is correct
171 Correct 245 ms 136676 KB Output is correct
172 Correct 162 ms 136652 KB Output is correct
173 Correct 552 ms 147244 KB Output is correct
174 Correct 437 ms 138860 KB Output is correct
175 Correct 326 ms 136920 KB Output is correct
176 Correct 167 ms 136600 KB Output is correct
177 Correct 543 ms 145612 KB Output is correct
178 Correct 421 ms 138444 KB Output is correct
179 Correct 320 ms 136836 KB Output is correct
180 Correct 165 ms 136580 KB Output is correct
181 Correct 197 ms 142456 KB Output is correct
182 Correct 237 ms 143672 KB Output is correct
183 Correct 168 ms 142220 KB Output is correct
184 Correct 204 ms 143392 KB Output is correct
185 Correct 188 ms 142456 KB Output is correct
186 Correct 231 ms 143600 KB Output is correct
187 Correct 168 ms 142244 KB Output is correct
188 Correct 207 ms 143428 KB Output is correct
189 Correct 188 ms 142532 KB Output is correct
190 Correct 231 ms 143664 KB Output is correct
191 Correct 194 ms 152012 KB Output is correct
192 Correct 196 ms 151996 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 213460 KB Output is correct
2 Correct 558 ms 213448 KB Output is correct
3 Correct 967 ms 295012 KB Output is correct
4 Correct 1018 ms 295172 KB Output is correct
5 Correct 1212 ms 336032 KB Output is correct
6 Correct 1309 ms 336156 KB Output is correct
7 Correct 3686 ms 170356 KB Output is correct
8 Correct 2430 ms 147820 KB Output is correct
9 Correct 2374 ms 145608 KB Output is correct
10 Correct 3590 ms 171708 KB Output is correct
11 Correct 2453 ms 147852 KB Output is correct
12 Correct 2341 ms 145664 KB Output is correct
13 Correct 3793 ms 173532 KB Output is correct
14 Correct 2442 ms 148052 KB Output is correct
15 Correct 2305 ms 145528 KB Output is correct
16 Correct 1914 ms 165800 KB Output is correct
17 Correct 1885 ms 165780 KB Output is correct
18 Correct 1862 ms 165744 KB Output is correct
19 Correct 1901 ms 165844 KB Output is correct
20 Correct 1858 ms 166016 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 131732 KB Output is correct
2 Correct 65 ms 131636 KB Output is correct
3 Correct 67 ms 131660 KB Output is correct
4 Correct 64 ms 131640 KB Output is correct
5 Correct 66 ms 131708 KB Output is correct
6 Correct 65 ms 131612 KB Output is correct
7 Correct 65 ms 131600 KB Output is correct
8 Correct 65 ms 131660 KB Output is correct
9 Correct 65 ms 131704 KB Output is correct
10 Correct 64 ms 131716 KB Output is correct
11 Correct 65 ms 131776 KB Output is correct
12 Correct 65 ms 131660 KB Output is correct
13 Correct 65 ms 131872 KB Output is correct
14 Correct 66 ms 131760 KB Output is correct
15 Correct 64 ms 131812 KB Output is correct
16 Correct 67 ms 131764 KB Output is correct
17 Correct 66 ms 131672 KB Output is correct
18 Correct 64 ms 131620 KB Output is correct
19 Correct 64 ms 131588 KB Output is correct
20 Correct 64 ms 131588 KB Output is correct
21 Correct 65 ms 131656 KB Output is correct
22 Correct 65 ms 131820 KB Output is correct
23 Correct 65 ms 131600 KB Output is correct
24 Correct 70 ms 131660 KB Output is correct
25 Correct 66 ms 131808 KB Output is correct
26 Correct 64 ms 131772 KB Output is correct
27 Correct 66 ms 131744 KB Output is correct
28 Correct 64 ms 131788 KB Output is correct
29 Correct 70 ms 131856 KB Output is correct
30 Correct 66 ms 131832 KB Output is correct
31 Correct 67 ms 131748 KB Output is correct
32 Correct 66 ms 131736 KB Output is correct
33 Correct 63 ms 131780 KB Output is correct
34 Correct 64 ms 131616 KB Output is correct
35 Correct 64 ms 131660 KB Output is correct
36 Correct 65 ms 131620 KB Output is correct
37 Correct 65 ms 131684 KB Output is correct
38 Correct 64 ms 131624 KB Output is correct
39 Correct 65 ms 131676 KB Output is correct
40 Correct 67 ms 131640 KB Output is correct
41 Correct 67 ms 131788 KB Output is correct
42 Correct 64 ms 131572 KB Output is correct
43 Correct 64 ms 131572 KB Output is correct
44 Correct 64 ms 131676 KB Output is correct
45 Correct 65 ms 131636 KB Output is correct
46 Correct 63 ms 131624 KB Output is correct
47 Correct 63 ms 131600 KB Output is correct
48 Correct 66 ms 131644 KB Output is correct
49 Correct 64 ms 131632 KB Output is correct
50 Correct 64 ms 131704 KB Output is correct
51 Correct 64 ms 131620 KB Output is correct
52 Correct 64 ms 131632 KB Output is correct
53 Correct 65 ms 131624 KB Output is correct
54 Correct 69 ms 131664 KB Output is correct
55 Correct 65 ms 131696 KB Output is correct
56 Correct 65 ms 131748 KB Output is correct
57 Correct 64 ms 131720 KB Output is correct
58 Correct 65 ms 131660 KB Output is correct
59 Correct 66 ms 131736 KB Output is correct
60 Correct 66 ms 131956 KB Output is correct
61 Correct 63 ms 131516 KB Output is correct
62 Correct 63 ms 131612 KB Output is correct
63 Correct 64 ms 131540 KB Output is correct
64 Correct 130 ms 135392 KB Output is correct
65 Correct 131 ms 133324 KB Output is correct
66 Correct 117 ms 132852 KB Output is correct
67 Correct 92 ms 132756 KB Output is correct
68 Correct 132 ms 135420 KB Output is correct
69 Correct 131 ms 133336 KB Output is correct
70 Correct 120 ms 132856 KB Output is correct
71 Correct 106 ms 132860 KB Output is correct
72 Correct 125 ms 136904 KB Output is correct
73 Correct 129 ms 136140 KB Output is correct
74 Correct 137 ms 136120 KB Output is correct
75 Correct 129 ms 135904 KB Output is correct
76 Correct 125 ms 137756 KB Output is correct
77 Correct 128 ms 137840 KB Output is correct
78 Correct 123 ms 137804 KB Output is correct
79 Correct 135 ms 137848 KB Output is correct
80 Correct 143 ms 135444 KB Output is correct
81 Correct 128 ms 133324 KB Output is correct
82 Correct 121 ms 132888 KB Output is correct
83 Correct 84 ms 132736 KB Output is correct
84 Correct 131 ms 135416 KB Output is correct
85 Correct 132 ms 133304 KB Output is correct
86 Correct 119 ms 132848 KB Output is correct
87 Correct 110 ms 132872 KB Output is correct
88 Correct 129 ms 136916 KB Output is correct
89 Correct 143 ms 136148 KB Output is correct
90 Correct 127 ms 135872 KB Output is correct
91 Correct 139 ms 135964 KB Output is correct
92 Correct 132 ms 137860 KB Output is correct
93 Correct 122 ms 137852 KB Output is correct
94 Correct 120 ms 137724 KB Output is correct
95 Correct 126 ms 137884 KB Output is correct
96 Correct 85 ms 132788 KB Output is correct
97 Correct 83 ms 132792 KB Output is correct
98 Correct 83 ms 132788 KB Output is correct
99 Correct 83 ms 132764 KB Output is correct
100 Correct 108 ms 132852 KB Output is correct
101 Correct 117 ms 132812 KB Output is correct
102 Correct 106 ms 132916 KB Output is correct
103 Correct 83 ms 132828 KB Output is correct
104 Correct 132 ms 135372 KB Output is correct
105 Correct 126 ms 133228 KB Output is correct
106 Correct 106 ms 132840 KB Output is correct
107 Correct 87 ms 132812 KB Output is correct
108 Correct 140 ms 134900 KB Output is correct
109 Correct 128 ms 133256 KB Output is correct
110 Correct 109 ms 132916 KB Output is correct
111 Correct 85 ms 132836 KB Output is correct
112 Correct 88 ms 134132 KB Output is correct
113 Correct 99 ms 134468 KB Output is correct
114 Correct 88 ms 134100 KB Output is correct
115 Correct 95 ms 134348 KB Output is correct
116 Correct 90 ms 134220 KB Output is correct
117 Correct 96 ms 134520 KB Output is correct
118 Correct 86 ms 134144 KB Output is correct
119 Correct 93 ms 134396 KB Output is correct
120 Correct 88 ms 134200 KB Output is correct
121 Correct 94 ms 134476 KB Output is correct
122 Correct 107 ms 136456 KB Output is correct
123 Correct 99 ms 136520 KB Output is correct
124 Correct 119 ms 133148 KB Output is correct
125 Correct 110 ms 132432 KB Output is correct
126 Correct 111 ms 132364 KB Output is correct
127 Correct 120 ms 133552 KB Output is correct
128 Correct 107 ms 132416 KB Output is correct
129 Correct 104 ms 132256 KB Output is correct
130 Correct 121 ms 133748 KB Output is correct
131 Correct 108 ms 132484 KB Output is correct
132 Correct 106 ms 132296 KB Output is correct
133 Correct 513 ms 147880 KB Output is correct
134 Correct 445 ms 138904 KB Output is correct
135 Correct 368 ms 136912 KB Output is correct
136 Correct 182 ms 136636 KB Output is correct
137 Correct 506 ms 148064 KB Output is correct
138 Correct 475 ms 139012 KB Output is correct
139 Correct 364 ms 136956 KB Output is correct
140 Correct 293 ms 136736 KB Output is correct
141 Correct 508 ms 154444 KB Output is correct
142 Correct 488 ms 151352 KB Output is correct
143 Correct 455 ms 150280 KB Output is correct
144 Correct 468 ms 150056 KB Output is correct
145 Correct 449 ms 158284 KB Output is correct
146 Correct 426 ms 158244 KB Output is correct
147 Correct 433 ms 158288 KB Output is correct
148 Correct 451 ms 158172 KB Output is correct
149 Correct 506 ms 147824 KB Output is correct
150 Correct 460 ms 138872 KB Output is correct
151 Correct 363 ms 136892 KB Output is correct
152 Correct 169 ms 136544 KB Output is correct
153 Correct 523 ms 147916 KB Output is correct
154 Correct 455 ms 138860 KB Output is correct
155 Correct 357 ms 136872 KB Output is correct
156 Correct 304 ms 136604 KB Output is correct
157 Correct 488 ms 154656 KB Output is correct
158 Correct 523 ms 150992 KB Output is correct
159 Correct 462 ms 150204 KB Output is correct
160 Correct 461 ms 150008 KB Output is correct
161 Correct 435 ms 158200 KB Output is correct
162 Correct 431 ms 158116 KB Output is correct
163 Correct 434 ms 157812 KB Output is correct
164 Correct 423 ms 158028 KB Output is correct
165 Correct 167 ms 136648 KB Output is correct
166 Correct 165 ms 136596 KB Output is correct
167 Correct 149 ms 136548 KB Output is correct
168 Correct 156 ms 136784 KB Output is correct
169 Correct 314 ms 136696 KB Output is correct
170 Correct 246 ms 136744 KB Output is correct
171 Correct 245 ms 136676 KB Output is correct
172 Correct 162 ms 136652 KB Output is correct
173 Correct 552 ms 147244 KB Output is correct
174 Correct 437 ms 138860 KB Output is correct
175 Correct 326 ms 136920 KB Output is correct
176 Correct 167 ms 136600 KB Output is correct
177 Correct 543 ms 145612 KB Output is correct
178 Correct 421 ms 138444 KB Output is correct
179 Correct 320 ms 136836 KB Output is correct
180 Correct 165 ms 136580 KB Output is correct
181 Correct 197 ms 142456 KB Output is correct
182 Correct 237 ms 143672 KB Output is correct
183 Correct 168 ms 142220 KB Output is correct
184 Correct 204 ms 143392 KB Output is correct
185 Correct 188 ms 142456 KB Output is correct
186 Correct 231 ms 143600 KB Output is correct
187 Correct 168 ms 142244 KB Output is correct
188 Correct 207 ms 143428 KB Output is correct
189 Correct 188 ms 142532 KB Output is correct
190 Correct 231 ms 143664 KB Output is correct
191 Correct 194 ms 152012 KB Output is correct
192 Correct 196 ms 151996 KB Output is correct
193 Correct 554 ms 213460 KB Output is correct
194 Correct 558 ms 213448 KB Output is correct
195 Correct 967 ms 295012 KB Output is correct
196 Correct 1018 ms 295172 KB Output is correct
197 Correct 1212 ms 336032 KB Output is correct
198 Correct 1309 ms 336156 KB Output is correct
199 Correct 3686 ms 170356 KB Output is correct
200 Correct 2430 ms 147820 KB Output is correct
201 Correct 2374 ms 145608 KB Output is correct
202 Correct 3590 ms 171708 KB Output is correct
203 Correct 2453 ms 147852 KB Output is correct
204 Correct 2341 ms 145664 KB Output is correct
205 Correct 3793 ms 173532 KB Output is correct
206 Correct 2442 ms 148052 KB Output is correct
207 Correct 2305 ms 145528 KB Output is correct
208 Correct 1914 ms 165800 KB Output is correct
209 Correct 1885 ms 165780 KB Output is correct
210 Correct 1862 ms 165744 KB Output is correct
211 Correct 1901 ms 165844 KB Output is correct
212 Correct 1858 ms 166016 KB Output is correct
213 Execution timed out 7037 ms 296984 KB Time limit exceeded
214 Halted 0 ms 0 KB -