oj.uz

Submission #986591

# Submission time Handle Problem Language Result Execution time Memory
986591 2024-05-20T20:32:14 Z activedeltorre Interval Collection (CCO20_day2problem2) C++14
18 / 25
 7000 ms 338408 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
struct ura
{
    int a,b;
};
vector<ura>vec;
const int nmax=1000005;
int aint[nmax*4];
int aint2[nmax*4];
int inf=1e9+5;
int inter(int i,int j)
{
    return max(0,min(vec[i].b,vec[j].b)-max(vec[i].a,vec[j].a));
}
int reun(int i,int j)
{
    return max(vec[i].b,vec[j].b)-min(vec[i].a,vec[j].a);
}
int distsol,cost;
multiset<int>lfend;
multiset<int>rgend;
/// qr1 pe partea dreapta
struct undos
{
    int unde,pozupdate,delacat;
};
vector<undos>oper;
int qr1(int node,int st,int dr,int qst,int qdr)
{
    if(st>qdr || st>dr || qst>dr || qst>qdr)
    {
        return inf;
    }
    if(qst<=st && dr<=qdr)
    {
        return aint[node];
    }
    int mij=(st+dr)/2;
    return min(qr1(node*2,st,mij,qst,qdr),qr1(node*2+1,mij+1,dr,qst,qdr));
}
int qr2(int node,int st,int dr,int qst,int qdr)
{
    if(st>qdr || st>dr || qst>dr || qst>qdr)
    {
        return -inf;
    }
    if(qst<=st && dr<=qdr)
    {
        return aint2[node];
    }
    int mij=(st+dr)/2;
    return max(qr2(node*2,st,mij,qst,qdr),qr2(node*2+1,mij+1,dr,qst,qdr));
}
void update1(int node,int st,int dr,int poz,int val,int smech)
{
    if(st>poz || poz>dr)
    {
        return ;
    }
    if(poz<=st && dr<=poz)
    {
        if(smech==1)
        {
            aint[node]=val;
        }
        else
        {
            oper.push_back({1,poz,aint[node]});
            aint[node]=min(aint[node],val);
        }
        return;
    }
    int mij=(st+dr)/2;
    update1(node*2,st,mij,poz,val,smech);
    update1(node*2+1,mij+1,dr,poz,val,smech);
    aint[node]=min(aint[node*2],aint[node*2+1]);
}
void update2(int node,int st,int dr,int poz,int val,int smech)
{
    if(st>poz || poz>dr)
    {
        return ;
    }
    if(poz<=st && dr<=poz)
    {
        if(smech==1)
        {
            aint2[node]=val;
        }
        else
        {
            oper.push_back({2,poz,aint2[node]});
            aint2[node]=max(aint2[node],val);
        }
        return;
    }
    int mij=(st+dr)/2;
    update2(node*2,st,mij,poz,val,smech);
    update2(node*2+1,mij+1,dr,poz,val,smech);
    aint2[node]=max(aint2[node*2],aint2[node*2+1]);
}
void clr(int node,int st,int dr)
{
    aint2[node]=-inf;
    aint[node]=inf;
    if(st!=dr)
    {
        int mij=(st+dr)/2;
        clr(node*2,st,mij);
        clr(node*2+1,mij+1,dr);
    }
}
multiset<pair<int,int> >solutii;
void undo()
{
    undos a;
    a=oper.back();
    if(a.unde==1)
        update1(1,1,nmax,a.pozupdate,a.delacat,1);
    else if(a.unde==2)
        update2(1,1,nmax,a.pozupdate,a.delacat,1);
    else if(a.unde==3)
        solutii.erase(solutii.find({a.pozupdate,a.delacat}));
    else if(a.unde==4)
        rgend.erase(rgend.find(a.pozupdate));
    else
        lfend.erase(lfend.find(a.pozupdate));
    oper.pop_back();
}
void add(ura x)
{
    int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
    if(lfend.size() && x.b>*prev(lfend.end()))
    {
        supra=x.b-*prev(lfend.end());
        nosupra=qr1(1,1,nmax,*prev(lfend.end()),nmax)-x.a;
    }
    else if(lfend.size())
    {
        supra=0;
        nosupra=qr1(1,1,nmax,x.b,nmax)-x.a;
    }
    lfend.insert(x.a);
    update1(1,1,nmax,x.a,x.b,0);
    if(rgend.size() && x.a<=*rgend.begin())
    {
        supra1=*rgend.begin()-x.a;
        nosupra1=x.b-qr2(1,1,nmax,1,*rgend.begin());
    }
    else if(rgend.size())
    {
        supra1=0;
        nosupra1=x.b-qr2(1,1,nmax,1,x.a);
    }
    rgend.insert(x.b);
    update2(1,1,nmax,x.b,x.a,0);
    if(supra1<supra)
    {
        swap(supra1,supra);
        swap(nosupra1,nosupra);
    }
    else if(supra1==supra)
    {
        nosupra=min(nosupra1,nosupra);
    }
    if(supra>=x.b-x.a)
    {
        supra=x.b-x.a;
        nosupra=x.b-x.a;
    }
    solutii.insert({supra,nosupra});
    oper.push_back({3,supra,nosupra});
    oper.push_back({4,x.b,0});
    oper.push_back({5,x.a,0});
}
vector<ura>vectorus[nmax*4];
map<pair<int,int>,int>fre;
map<pair<int,int>,int>lst;
void dncadd(int node,int st,int dr,int qst,int qdr,int lf,int rg)
{
    if(st>qdr || st>dr || qst>dr || qst>qdr)
    {
        return ;
    }
    if(qst<=st && dr<=qdr)
    {
        vectorus[node].push_back({lf,rg});
        return;
    }
    int mij=(st+dr)/2;
    dncadd(node*2,st,mij,qst,qdr,lf,rg);
    dncadd(node*2+1,mij+1,dr,qst,qdr,lf,rg);
}
void dfsdnc(int curr,int st,int dr)
{
    int number=oper.size();
    for(int j=0;j<vectorus[curr].size();j++)
    {
        add(vectorus[curr][j]);
    }
    if(st==dr)
    {
        cout<<solutii.begin()->second<<'\n';
    }
    else
    {
        int mij=(st+dr)/2;
        dfsdnc(curr*2,st,mij);
        dfsdnc(curr*2+1,mij+1,dr);
    }
    while(oper.size()>number)
    {
        undo();
    }
}
int main()
{
    int n,i,j,k,l,r,z;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    char tip;
    for(i=1; i<=n; i++)
    {
        cin>>tip;
        if(tip=='A')
        {
            cin>>l>>r;
            l++;
            r++;
            fre[{l,r}]++;
            if(fre[{l,r}]==1)
            {
               lst[{l,r}]=i;
            }
        }
        else if(tip=='R')
        {
            cin>>l>>r;
            l++;
            r++;
            fre[{l,r}]--;
            if(fre[{l,r}]==0)
            {
                dncadd(1,1,n,lst[{l,r}],i-1,l,r);
            }
        }
    }
    for(auto j :fre)
    {
        if(j.second>0)
        {
            dncadd(1,1,n,lst[j.first],n,j.first.first,j.first.second);
        }
    }
    clr(1,1,nmax);
    dfsdnc(1,1,n);
    /*
    for(i=1; i<=n; i++)
    {
        distsol=inf;
        cost=0;
        lfend.clear();
        rgend.clear();
        solutii.clear();
        for(j=0; j<vecus[i].size(); j++)
        {
            add(vecus[i][j]);
        }
        cout<<solutii.begin()->second<<'\n';
        while(oper.size()>0)
        {
            undo();
        }
    }*/
    return 0;
}

Compilation message

Main.cpp: In function 'void add(ura)':
Main.cpp:137:9: warning: unused variable 'sol' [-Wunused-variable]
  137 |     int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
      |         ^~~
Main.cpp:137:17: warning: unused variable 'cost' [-Wunused-variable]
  137 |     int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
      |                 ^~~~
Main.cpp: In function 'void dfsdnc(int, int, int)':
Main.cpp:202:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for(int j=0;j<vectorus[curr].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:216:22: warning: comparison of integer expressions of different signedness: 'std::vector<undos>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  216 |     while(oper.size()>number)
      |           ~~~~~~~~~~~^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:223:13: warning: unused variable 'j' [-Wunused-variable]
  223 |     int n,i,j,k,l,r,z;
      |             ^
Main.cpp:223:15: warning: unused variable 'k' [-Wunused-variable]
  223 |     int n,i,j,k,l,r,z;
      |               ^
Main.cpp:223:21: warning: unused variable 'z' [-Wunused-variable]
  223 |     int n,i,j,k,l,r,z;
      |                     ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110820 KB Output is correct
2 Correct 57 ms 110884 KB Output is correct
3 Correct 57 ms 110676 KB Output is correct
4 Correct 54 ms 110684 KB Output is correct
5 Correct 56 ms 110928 KB Output is correct
6 Correct 53 ms 110676 KB Output is correct
7 Correct 53 ms 110652 KB Output is correct
8 Correct 64 ms 110844 KB Output is correct
9 Correct 56 ms 110936 KB Output is correct
10 Correct 54 ms 110968 KB Output is correct
11 Correct 58 ms 110760 KB Output is correct
12 Correct 59 ms 110932 KB Output is correct
13 Correct 61 ms 110828 KB Output is correct
14 Correct 57 ms 110928 KB Output is correct
15 Correct 59 ms 110932 KB Output is correct
16 Correct 63 ms 110928 KB Output is correct
17 Correct 65 ms 110928 KB Output is correct
18 Correct 58 ms 110676 KB Output is correct
19 Correct 57 ms 110676 KB Output is correct
20 Correct 56 ms 110676 KB Output is correct
21 Correct 58 ms 110860 KB Output is correct
22 Correct 57 ms 110668 KB Output is correct
23 Correct 61 ms 110672 KB Output is correct
24 Correct 58 ms 110672 KB Output is correct
25 Correct 59 ms 110864 KB Output is correct
26 Correct 60 ms 110932 KB Output is correct
27 Correct 61 ms 110964 KB Output is correct
28 Correct 59 ms 110896 KB Output is correct
29 Correct 59 ms 110932 KB Output is correct
30 Correct 67 ms 111020 KB Output is correct
31 Correct 67 ms 110852 KB Output is correct
32 Correct 60 ms 110924 KB Output is correct
33 Correct 56 ms 110856 KB Output is correct
34 Correct 56 ms 110676 KB Output is correct
35 Correct 55 ms 110672 KB Output is correct
36 Correct 59 ms 110932 KB Output is correct
37 Correct 57 ms 110668 KB Output is correct
38 Correct 57 ms 110820 KB Output is correct
39 Correct 56 ms 110664 KB Output is correct
40 Correct 56 ms 110672 KB Output is correct
41 Correct 60 ms 111128 KB Output is correct
42 Correct 58 ms 110872 KB Output is correct
43 Correct 65 ms 110672 KB Output is correct
44 Correct 58 ms 110864 KB Output is correct
45 Correct 60 ms 110928 KB Output is correct
46 Correct 58 ms 110676 KB Output is correct
47 Correct 60 ms 110712 KB Output is correct
48 Correct 57 ms 110672 KB Output is correct
49 Correct 58 ms 110932 KB Output is correct
50 Correct 57 ms 110856 KB Output is correct
51 Correct 59 ms 110944 KB Output is correct
52 Correct 58 ms 110932 KB Output is correct
53 Correct 66 ms 110732 KB Output is correct
54 Correct 58 ms 110932 KB Output is correct
55 Correct 59 ms 110932 KB Output is correct
56 Correct 58 ms 110932 KB Output is correct
57 Correct 64 ms 110692 KB Output is correct
58 Correct 58 ms 110788 KB Output is correct
59 Correct 58 ms 111016 KB Output is correct
60 Correct 59 ms 110936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110820 KB Output is correct
2 Correct 57 ms 110884 KB Output is correct
3 Correct 57 ms 110676 KB Output is correct
4 Correct 54 ms 110684 KB Output is correct
5 Correct 56 ms 110928 KB Output is correct
6 Correct 53 ms 110676 KB Output is correct
7 Correct 53 ms 110652 KB Output is correct
8 Correct 64 ms 110844 KB Output is correct
9 Correct 56 ms 110936 KB Output is correct
10 Correct 54 ms 110968 KB Output is correct
11 Correct 58 ms 110760 KB Output is correct
12 Correct 59 ms 110932 KB Output is correct
13 Correct 61 ms 110828 KB Output is correct
14 Correct 57 ms 110928 KB Output is correct
15 Correct 59 ms 110932 KB Output is correct
16 Correct 63 ms 110928 KB Output is correct
17 Correct 65 ms 110928 KB Output is correct
18 Correct 58 ms 110676 KB Output is correct
19 Correct 57 ms 110676 KB Output is correct
20 Correct 56 ms 110676 KB Output is correct
21 Correct 58 ms 110860 KB Output is correct
22 Correct 57 ms 110668 KB Output is correct
23 Correct 61 ms 110672 KB Output is correct
24 Correct 58 ms 110672 KB Output is correct
25 Correct 59 ms 110864 KB Output is correct
26 Correct 60 ms 110932 KB Output is correct
27 Correct 61 ms 110964 KB Output is correct
28 Correct 59 ms 110896 KB Output is correct
29 Correct 59 ms 110932 KB Output is correct
30 Correct 67 ms 111020 KB Output is correct
31 Correct 67 ms 110852 KB Output is correct
32 Correct 60 ms 110924 KB Output is correct
33 Correct 56 ms 110856 KB Output is correct
34 Correct 56 ms 110676 KB Output is correct
35 Correct 55 ms 110672 KB Output is correct
36 Correct 59 ms 110932 KB Output is correct
37 Correct 57 ms 110668 KB Output is correct
38 Correct 57 ms 110820 KB Output is correct
39 Correct 56 ms 110664 KB Output is correct
40 Correct 56 ms 110672 KB Output is correct
41 Correct 60 ms 111128 KB Output is correct
42 Correct 58 ms 110872 KB Output is correct
43 Correct 65 ms 110672 KB Output is correct
44 Correct 58 ms 110864 KB Output is correct
45 Correct 60 ms 110928 KB Output is correct
46 Correct 58 ms 110676 KB Output is correct
47 Correct 60 ms 110712 KB Output is correct
48 Correct 57 ms 110672 KB Output is correct
49 Correct 58 ms 110932 KB Output is correct
50 Correct 57 ms 110856 KB Output is correct
51 Correct 59 ms 110944 KB Output is correct
52 Correct 58 ms 110932 KB Output is correct
53 Correct 66 ms 110732 KB Output is correct
54 Correct 58 ms 110932 KB Output is correct
55 Correct 59 ms 110932 KB Output is correct
56 Correct 58 ms 110932 KB Output is correct
57 Correct 64 ms 110692 KB Output is correct
58 Correct 58 ms 110788 KB Output is correct
59 Correct 58 ms 111016 KB Output is correct
60 Correct 59 ms 110936 KB Output is correct
61 Correct 56 ms 110808 KB Output is correct
62 Correct 57 ms 110672 KB Output is correct
63 Correct 56 ms 110680 KB Output is correct
64 Correct 207 ms 114584 KB Output is correct
65 Correct 186 ms 113368 KB Output is correct
66 Correct 129 ms 112624 KB Output is correct
67 Correct 75 ms 112144 KB Output is correct
68 Correct 209 ms 114428 KB Output is correct
69 Correct 167 ms 112976 KB Output is correct
70 Correct 131 ms 112700 KB Output is correct
71 Correct 110 ms 112468 KB Output is correct
72 Correct 233 ms 115548 KB Output is correct
73 Correct 219 ms 115104 KB Output is correct
74 Correct 207 ms 114928 KB Output is correct
75 Correct 199 ms 115084 KB Output is correct
76 Correct 218 ms 116196 KB Output is correct
77 Correct 231 ms 115928 KB Output is correct
78 Correct 217 ms 115920 KB Output is correct
79 Correct 249 ms 116000 KB Output is correct
80 Correct 234 ms 114472 KB Output is correct
81 Correct 163 ms 113112 KB Output is correct
82 Correct 128 ms 112536 KB Output is correct
83 Correct 78 ms 112080 KB Output is correct
84 Correct 212 ms 114448 KB Output is correct
85 Correct 164 ms 112976 KB Output is correct
86 Correct 130 ms 112688 KB Output is correct
87 Correct 115 ms 112460 KB Output is correct
88 Correct 216 ms 115260 KB Output is correct
89 Correct 203 ms 114952 KB Output is correct
90 Correct 197 ms 114948 KB Output is correct
91 Correct 197 ms 114912 KB Output is correct
92 Correct 234 ms 116104 KB Output is correct
93 Correct 221 ms 115876 KB Output is correct
94 Correct 255 ms 115996 KB Output is correct
95 Correct 223 ms 115976 KB Output is correct
96 Correct 76 ms 112120 KB Output is correct
97 Correct 75 ms 112016 KB Output is correct
98 Correct 77 ms 111952 KB Output is correct
99 Correct 76 ms 112052 KB Output is correct
100 Correct 119 ms 112452 KB Output is correct
101 Correct 102 ms 112236 KB Output is correct
102 Correct 117 ms 112720 KB Output is correct
103 Correct 78 ms 111952 KB Output is correct
104 Correct 192 ms 114320 KB Output is correct
105 Correct 156 ms 113024 KB Output is correct
106 Correct 133 ms 112444 KB Output is correct
107 Correct 78 ms 112172 KB Output is correct
108 Correct 212 ms 114024 KB Output is correct
109 Correct 154 ms 112868 KB Output is correct
110 Correct 121 ms 112496 KB Output is correct
111 Correct 79 ms 111956 KB Output is correct
112 Correct 117 ms 113860 KB Output is correct
113 Correct 128 ms 113940 KB Output is correct
114 Correct 114 ms 113804 KB Output is correct
115 Correct 125 ms 113804 KB Output is correct
116 Correct 116 ms 113808 KB Output is correct
117 Correct 134 ms 113796 KB Output is correct
118 Correct 115 ms 113880 KB Output is correct
119 Correct 130 ms 113960 KB Output is correct
120 Correct 121 ms 114064 KB Output is correct
121 Correct 140 ms 113888 KB Output is correct
122 Correct 210 ms 115892 KB Output is correct
123 Correct 176 ms 115792 KB Output is correct
124 Correct 153 ms 112932 KB Output is correct
125 Correct 132 ms 112356 KB Output is correct
126 Correct 124 ms 112120 KB Output is correct
127 Correct 164 ms 113264 KB Output is correct
128 Correct 131 ms 112244 KB Output is correct
129 Correct 123 ms 112208 KB Output is correct
130 Correct 166 ms 113564 KB Output is correct
131 Correct 129 ms 112208 KB Output is correct
132 Correct 125 ms 112160 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110820 KB Output is correct
2 Correct 57 ms 110884 KB Output is correct
3 Correct 57 ms 110676 KB Output is correct
4 Correct 54 ms 110684 KB Output is correct
5 Correct 56 ms 110928 KB Output is correct
6 Correct 53 ms 110676 KB Output is correct
7 Correct 53 ms 110652 KB Output is correct
8 Correct 64 ms 110844 KB Output is correct
9 Correct 56 ms 110936 KB Output is correct
10 Correct 54 ms 110968 KB Output is correct
11 Correct 58 ms 110760 KB Output is correct
12 Correct 59 ms 110932 KB Output is correct
13 Correct 61 ms 110828 KB Output is correct
14 Correct 57 ms 110928 KB Output is correct
15 Correct 59 ms 110932 KB Output is correct
16 Correct 63 ms 110928 KB Output is correct
17 Correct 65 ms 110928 KB Output is correct
18 Correct 58 ms 110676 KB Output is correct
19 Correct 57 ms 110676 KB Output is correct
20 Correct 56 ms 110676 KB Output is correct
21 Correct 58 ms 110860 KB Output is correct
22 Correct 57 ms 110668 KB Output is correct
23 Correct 61 ms 110672 KB Output is correct
24 Correct 58 ms 110672 KB Output is correct
25 Correct 59 ms 110864 KB Output is correct
26 Correct 60 ms 110932 KB Output is correct
27 Correct 61 ms 110964 KB Output is correct
28 Correct 59 ms 110896 KB Output is correct
29 Correct 59 ms 110932 KB Output is correct
30 Correct 67 ms 111020 KB Output is correct
31 Correct 67 ms 110852 KB Output is correct
32 Correct 60 ms 110924 KB Output is correct
33 Correct 56 ms 110856 KB Output is correct
34 Correct 56 ms 110676 KB Output is correct
35 Correct 55 ms 110672 KB Output is correct
36 Correct 59 ms 110932 KB Output is correct
37 Correct 57 ms 110668 KB Output is correct
38 Correct 57 ms 110820 KB Output is correct
39 Correct 56 ms 110664 KB Output is correct
40 Correct 56 ms 110672 KB Output is correct
41 Correct 60 ms 111128 KB Output is correct
42 Correct 58 ms 110872 KB Output is correct
43 Correct 65 ms 110672 KB Output is correct
44 Correct 58 ms 110864 KB Output is correct
45 Correct 60 ms 110928 KB Output is correct
46 Correct 58 ms 110676 KB Output is correct
47 Correct 60 ms 110712 KB Output is correct
48 Correct 57 ms 110672 KB Output is correct
49 Correct 58 ms 110932 KB Output is correct
50 Correct 57 ms 110856 KB Output is correct
51 Correct 59 ms 110944 KB Output is correct
52 Correct 58 ms 110932 KB Output is correct
53 Correct 66 ms 110732 KB Output is correct
54 Correct 58 ms 110932 KB Output is correct
55 Correct 59 ms 110932 KB Output is correct
56 Correct 58 ms 110932 KB Output is correct
57 Correct 64 ms 110692 KB Output is correct
58 Correct 58 ms 110788 KB Output is correct
59 Correct 58 ms 111016 KB Output is correct
60 Correct 59 ms 110936 KB Output is correct
61 Correct 56 ms 110808 KB Output is correct
62 Correct 57 ms 110672 KB Output is correct
63 Correct 56 ms 110680 KB Output is correct
64 Correct 207 ms 114584 KB Output is correct
65 Correct 186 ms 113368 KB Output is correct
66 Correct 129 ms 112624 KB Output is correct
67 Correct 75 ms 112144 KB Output is correct
68 Correct 209 ms 114428 KB Output is correct
69 Correct 167 ms 112976 KB Output is correct
70 Correct 131 ms 112700 KB Output is correct
71 Correct 110 ms 112468 KB Output is correct
72 Correct 233 ms 115548 KB Output is correct
73 Correct 219 ms 115104 KB Output is correct
74 Correct 207 ms 114928 KB Output is correct
75 Correct 199 ms 115084 KB Output is correct
76 Correct 218 ms 116196 KB Output is correct
77 Correct 231 ms 115928 KB Output is correct
78 Correct 217 ms 115920 KB Output is correct
79 Correct 249 ms 116000 KB Output is correct
80 Correct 234 ms 114472 KB Output is correct
81 Correct 163 ms 113112 KB Output is correct
82 Correct 128 ms 112536 KB Output is correct
83 Correct 78 ms 112080 KB Output is correct
84 Correct 212 ms 114448 KB Output is correct
85 Correct 164 ms 112976 KB Output is correct
86 Correct 130 ms 112688 KB Output is correct
87 Correct 115 ms 112460 KB Output is correct
88 Correct 216 ms 115260 KB Output is correct
89 Correct 203 ms 114952 KB Output is correct
90 Correct 197 ms 114948 KB Output is correct
91 Correct 197 ms 114912 KB Output is correct
92 Correct 234 ms 116104 KB Output is correct
93 Correct 221 ms 115876 KB Output is correct
94 Correct 255 ms 115996 KB Output is correct
95 Correct 223 ms 115976 KB Output is correct
96 Correct 76 ms 112120 KB Output is correct
97 Correct 75 ms 112016 KB Output is correct
98 Correct 77 ms 111952 KB Output is correct
99 Correct 76 ms 112052 KB Output is correct
100 Correct 119 ms 112452 KB Output is correct
101 Correct 102 ms 112236 KB Output is correct
102 Correct 117 ms 112720 KB Output is correct
103 Correct 78 ms 111952 KB Output is correct
104 Correct 192 ms 114320 KB Output is correct
105 Correct 156 ms 113024 KB Output is correct
106 Correct 133 ms 112444 KB Output is correct
107 Correct 78 ms 112172 KB Output is correct
108 Correct 212 ms 114024 KB Output is correct
109 Correct 154 ms 112868 KB Output is correct
110 Correct 121 ms 112496 KB Output is correct
111 Correct 79 ms 111956 KB Output is correct
112 Correct 117 ms 113860 KB Output is correct
113 Correct 128 ms 113940 KB Output is correct
114 Correct 114 ms 113804 KB Output is correct
115 Correct 125 ms 113804 KB Output is correct
116 Correct 116 ms 113808 KB Output is correct
117 Correct 134 ms 113796 KB Output is correct
118 Correct 115 ms 113880 KB Output is correct
119 Correct 130 ms 113960 KB Output is correct
120 Correct 121 ms 114064 KB Output is correct
121 Correct 140 ms 113888 KB Output is correct
122 Correct 210 ms 115892 KB Output is correct
123 Correct 176 ms 115792 KB Output is correct
124 Correct 153 ms 112932 KB Output is correct
125 Correct 132 ms 112356 KB Output is correct
126 Correct 124 ms 112120 KB Output is correct
127 Correct 164 ms 113264 KB Output is correct
128 Correct 131 ms 112244 KB Output is correct
129 Correct 123 ms 112208 KB Output is correct
130 Correct 166 ms 113564 KB Output is correct
131 Correct 129 ms 112208 KB Output is correct
132 Correct 125 ms 112160 KB Output is correct
133 Correct 983 ms 126304 KB Output is correct
134 Correct 684 ms 120956 KB Output is correct
135 Correct 473 ms 119124 KB Output is correct
136 Correct 186 ms 116820 KB Output is correct
137 Correct 934 ms 126216 KB Output is correct
138 Correct 684 ms 120636 KB Output is correct
139 Correct 491 ms 119120 KB Output is correct
140 Correct 359 ms 118100 KB Output is correct
141 Correct 1014 ms 130316 KB Output is correct
142 Correct 912 ms 128704 KB Output is correct
143 Correct 870 ms 128516 KB Output is correct
144 Correct 854 ms 128560 KB Output is correct
145 Correct 997 ms 133116 KB Output is correct
146 Correct 986 ms 132936 KB Output is correct
147 Correct 1028 ms 132752 KB Output is correct
148 Correct 1091 ms 132828 KB Output is correct
149 Correct 950 ms 126316 KB Output is correct
150 Correct 691 ms 120868 KB Output is correct
151 Correct 482 ms 119120 KB Output is correct
152 Correct 186 ms 116816 KB Output is correct
153 Correct 957 ms 126032 KB Output is correct
154 Correct 678 ms 120780 KB Output is correct
155 Correct 472 ms 118972 KB Output is correct
156 Correct 365 ms 118048 KB Output is correct
157 Correct 1055 ms 130408 KB Output is correct
158 Correct 915 ms 128568 KB Output is correct
159 Correct 892 ms 128676 KB Output is correct
160 Correct 940 ms 128664 KB Output is correct
161 Correct 1016 ms 132900 KB Output is correct
162 Correct 1082 ms 132736 KB Output is correct
163 Correct 1038 ms 132816 KB Output is correct
164 Correct 996 ms 132824 KB Output is correct
165 Correct 146 ms 116392 KB Output is correct
166 Correct 146 ms 116308 KB Output is correct
167 Correct 145 ms 116304 KB Output is correct
168 Correct 151 ms 116336 KB Output is correct
169 Correct 376 ms 118356 KB Output is correct
170 Correct 302 ms 117840 KB Output is correct
171 Correct 317 ms 117584 KB Output is correct
172 Correct 168 ms 116564 KB Output is correct
173 Correct 900 ms 126068 KB Output is correct
174 Correct 650 ms 120460 KB Output is correct
175 Correct 424 ms 118624 KB Output is correct
176 Correct 190 ms 116624 KB Output is correct
177 Correct 883 ms 124584 KB Output is correct
178 Correct 630 ms 119952 KB Output is correct
179 Correct 430 ms 118924 KB Output is correct
180 Correct 186 ms 116612 KB Output is correct
181 Correct 357 ms 124288 KB Output is correct
182 Correct 450 ms 124380 KB Output is correct
183 Correct 360 ms 124288 KB Output is correct
184 Correct 415 ms 124408 KB Output is correct
185 Correct 359 ms 124292 KB Output is correct
186 Correct 429 ms 124292 KB Output is correct
187 Correct 359 ms 124284 KB Output is correct
188 Correct 413 ms 124308 KB Output is correct
189 Correct 381 ms 124300 KB Output is correct
190 Correct 424 ms 124292 KB Output is correct
191 Correct 617 ms 132472 KB Output is correct
192 Correct 643 ms 132448 KB Output is correct

Subtask #4
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2799 ms 199744 KB Output is correct
2 Correct 2885 ms 199700 KB Output is correct
3 Correct 6159 ms 290340 KB Output is correct
4 Correct 6176 ms 290164 KB Output is correct
5 Execution timed out 7026 ms 338408 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110820 KB Output is correct
2 Correct 57 ms 110884 KB Output is correct
3 Correct 57 ms 110676 KB Output is correct
4 Correct 54 ms 110684 KB Output is correct
5 Correct 56 ms 110928 KB Output is correct
6 Correct 53 ms 110676 KB Output is correct
7 Correct 53 ms 110652 KB Output is correct
8 Correct 64 ms 110844 KB Output is correct
9 Correct 56 ms 110936 KB Output is correct
10 Correct 54 ms 110968 KB Output is correct
11 Correct 58 ms 110760 KB Output is correct
12 Correct 59 ms 110932 KB Output is correct
13 Correct 61 ms 110828 KB Output is correct
14 Correct 57 ms 110928 KB Output is correct
15 Correct 59 ms 110932 KB Output is correct
16 Correct 63 ms 110928 KB Output is correct
17 Correct 65 ms 110928 KB Output is correct
18 Correct 58 ms 110676 KB Output is correct
19 Correct 57 ms 110676 KB Output is correct
20 Correct 56 ms 110676 KB Output is correct
21 Correct 58 ms 110860 KB Output is correct
22 Correct 57 ms 110668 KB Output is correct
23 Correct 61 ms 110672 KB Output is correct
24 Correct 58 ms 110672 KB Output is correct
25 Correct 59 ms 110864 KB Output is correct
26 Correct 60 ms 110932 KB Output is correct
27 Correct 61 ms 110964 KB Output is correct
28 Correct 59 ms 110896 KB Output is correct
29 Correct 59 ms 110932 KB Output is correct
30 Correct 67 ms 111020 KB Output is correct
31 Correct 67 ms 110852 KB Output is correct
32 Correct 60 ms 110924 KB Output is correct
33 Correct 56 ms 110856 KB Output is correct
34 Correct 56 ms 110676 KB Output is correct
35 Correct 55 ms 110672 KB Output is correct
36 Correct 59 ms 110932 KB Output is correct
37 Correct 57 ms 110668 KB Output is correct
38 Correct 57 ms 110820 KB Output is correct
39 Correct 56 ms 110664 KB Output is correct
40 Correct 56 ms 110672 KB Output is correct
41 Correct 60 ms 111128 KB Output is correct
42 Correct 58 ms 110872 KB Output is correct
43 Correct 65 ms 110672 KB Output is correct
44 Correct 58 ms 110864 KB Output is correct
45 Correct 60 ms 110928 KB Output is correct
46 Correct 58 ms 110676 KB Output is correct
47 Correct 60 ms 110712 KB Output is correct
48 Correct 57 ms 110672 KB Output is correct
49 Correct 58 ms 110932 KB Output is correct
50 Correct 57 ms 110856 KB Output is correct
51 Correct 59 ms 110944 KB Output is correct
52 Correct 58 ms 110932 KB Output is correct
53 Correct 66 ms 110732 KB Output is correct
54 Correct 58 ms 110932 KB Output is correct
55 Correct 59 ms 110932 KB Output is correct
56 Correct 58 ms 110932 KB Output is correct
57 Correct 64 ms 110692 KB Output is correct
58 Correct 58 ms 110788 KB Output is correct
59 Correct 58 ms 111016 KB Output is correct
60 Correct 59 ms 110936 KB Output is correct
61 Correct 56 ms 110808 KB Output is correct
62 Correct 57 ms 110672 KB Output is correct
63 Correct 56 ms 110680 KB Output is correct
64 Correct 207 ms 114584 KB Output is correct
65 Correct 186 ms 113368 KB Output is correct
66 Correct 129 ms 112624 KB Output is correct
67 Correct 75 ms 112144 KB Output is correct
68 Correct 209 ms 114428 KB Output is correct
69 Correct 167 ms 112976 KB Output is correct
70 Correct 131 ms 112700 KB Output is correct
71 Correct 110 ms 112468 KB Output is correct
72 Correct 233 ms 115548 KB Output is correct
73 Correct 219 ms 115104 KB Output is correct
74 Correct 207 ms 114928 KB Output is correct
75 Correct 199 ms 115084 KB Output is correct
76 Correct 218 ms 116196 KB Output is correct
77 Correct 231 ms 115928 KB Output is correct
78 Correct 217 ms 115920 KB Output is correct
79 Correct 249 ms 116000 KB Output is correct
80 Correct 234 ms 114472 KB Output is correct
81 Correct 163 ms 113112 KB Output is correct
82 Correct 128 ms 112536 KB Output is correct
83 Correct 78 ms 112080 KB Output is correct
84 Correct 212 ms 114448 KB Output is correct
85 Correct 164 ms 112976 KB Output is correct
86 Correct 130 ms 112688 KB Output is correct
87 Correct 115 ms 112460 KB Output is correct
88 Correct 216 ms 115260 KB Output is correct
89 Correct 203 ms 114952 KB Output is correct
90 Correct 197 ms 114948 KB Output is correct
91 Correct 197 ms 114912 KB Output is correct
92 Correct 234 ms 116104 KB Output is correct
93 Correct 221 ms 115876 KB Output is correct
94 Correct 255 ms 115996 KB Output is correct
95 Correct 223 ms 115976 KB Output is correct
96 Correct 76 ms 112120 KB Output is correct
97 Correct 75 ms 112016 KB Output is correct
98 Correct 77 ms 111952 KB Output is correct
99 Correct 76 ms 112052 KB Output is correct
100 Correct 119 ms 112452 KB Output is correct
101 Correct 102 ms 112236 KB Output is correct
102 Correct 117 ms 112720 KB Output is correct
103 Correct 78 ms 111952 KB Output is correct
104 Correct 192 ms 114320 KB Output is correct
105 Correct 156 ms 113024 KB Output is correct
106 Correct 133 ms 112444 KB Output is correct
107 Correct 78 ms 112172 KB Output is correct
108 Correct 212 ms 114024 KB Output is correct
109 Correct 154 ms 112868 KB Output is correct
110 Correct 121 ms 112496 KB Output is correct
111 Correct 79 ms 111956 KB Output is correct
112 Correct 117 ms 113860 KB Output is correct
113 Correct 128 ms 113940 KB Output is correct
114 Correct 114 ms 113804 KB Output is correct
115 Correct 125 ms 113804 KB Output is correct
116 Correct 116 ms 113808 KB Output is correct
117 Correct 134 ms 113796 KB Output is correct
118 Correct 115 ms 113880 KB Output is correct
119 Correct 130 ms 113960 KB Output is correct
120 Correct 121 ms 114064 KB Output is correct
121 Correct 140 ms 113888 KB Output is correct
122 Correct 210 ms 115892 KB Output is correct
123 Correct 176 ms 115792 KB Output is correct
124 Correct 153 ms 112932 KB Output is correct
125 Correct 132 ms 112356 KB Output is correct
126 Correct 124 ms 112120 KB Output is correct
127 Correct 164 ms 113264 KB Output is correct
128 Correct 131 ms 112244 KB Output is correct
129 Correct 123 ms 112208 KB Output is correct
130 Correct 166 ms 113564 KB Output is correct
131 Correct 129 ms 112208 KB Output is correct
132 Correct 125 ms 112160 KB Output is correct
133 Correct 983 ms 126304 KB Output is correct
134 Correct 684 ms 120956 KB Output is correct
135 Correct 473 ms 119124 KB Output is correct
136 Correct 186 ms 116820 KB Output is correct
137 Correct 934 ms 126216 KB Output is correct
138 Correct 684 ms 120636 KB Output is correct
139 Correct 491 ms 119120 KB Output is correct
140 Correct 359 ms 118100 KB Output is correct
141 Correct 1014 ms 130316 KB Output is correct
142 Correct 912 ms 128704 KB Output is correct
143 Correct 870 ms 128516 KB Output is correct
144 Correct 854 ms 128560 KB Output is correct
145 Correct 997 ms 133116 KB Output is correct
146 Correct 986 ms 132936 KB Output is correct
147 Correct 1028 ms 132752 KB Output is correct
148 Correct 1091 ms 132828 KB Output is correct
149 Correct 950 ms 126316 KB Output is correct
150 Correct 691 ms 120868 KB Output is correct
151 Correct 482 ms 119120 KB Output is correct
152 Correct 186 ms 116816 KB Output is correct
153 Correct 957 ms 126032 KB Output is correct
154 Correct 678 ms 120780 KB Output is correct
155 Correct 472 ms 118972 KB Output is correct
156 Correct 365 ms 118048 KB Output is correct
157 Correct 1055 ms 130408 KB Output is correct
158 Correct 915 ms 128568 KB Output is correct
159 Correct 892 ms 128676 KB Output is correct
160 Correct 940 ms 128664 KB Output is correct
161 Correct 1016 ms 132900 KB Output is correct
162 Correct 1082 ms 132736 KB Output is correct
163 Correct 1038 ms 132816 KB Output is correct
164 Correct 996 ms 132824 KB Output is correct
165 Correct 146 ms 116392 KB Output is correct
166 Correct 146 ms 116308 KB Output is correct
167 Correct 145 ms 116304 KB Output is correct
168 Correct 151 ms 116336 KB Output is correct
169 Correct 376 ms 118356 KB Output is correct
170 Correct 302 ms 117840 KB Output is correct
171 Correct 317 ms 117584 KB Output is correct
172 Correct 168 ms 116564 KB Output is correct
173 Correct 900 ms 126068 KB Output is correct
174 Correct 650 ms 120460 KB Output is correct
175 Correct 424 ms 118624 KB Output is correct
176 Correct 190 ms 116624 KB Output is correct
177 Correct 883 ms 124584 KB Output is correct
178 Correct 630 ms 119952 KB Output is correct
179 Correct 430 ms 118924 KB Output is correct
180 Correct 186 ms 116612 KB Output is correct
181 Correct 357 ms 124288 KB Output is correct
182 Correct 450 ms 124380 KB Output is correct
183 Correct 360 ms 124288 KB Output is correct
184 Correct 415 ms 124408 KB Output is correct
185 Correct 359 ms 124292 KB Output is correct
186 Correct 429 ms 124292 KB Output is correct
187 Correct 359 ms 124284 KB Output is correct
188 Correct 413 ms 124308 KB Output is correct
189 Correct 381 ms 124300 KB Output is correct
190 Correct 424 ms 124292 KB Output is correct
191 Correct 617 ms 132472 KB Output is correct
192 Correct 643 ms 132448 KB Output is correct
193 Correct 2799 ms 199744 KB Output is correct
194 Correct 2885 ms 199700 KB Output is correct
195 Correct 6159 ms 290340 KB Output is correct
196 Correct 6176 ms 290164 KB Output is correct
197 Execution timed out 7026 ms 338408 KB Time limit exceeded
198 Halted 0 ms 0 KB -