oj.uz

Submission #568745

# Submission time Handle Problem Language Result Execution time Memory
568745 2022-05-26T06:55:22 Z tqbfjotld Fish 2 (JOI22_fish2) C++14
100 / 100
 3941 ms 117532 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 999999999999999999LL;

struct dat{
    vector<int> lblockvals;
    vector<int> lblockpos;
    vector<int> lblocknum;
    vector<int> lblockpsum;
    vector<int> rblockvals;
    vector<int> rblockpos;
    vector<int> rblocknum;
    vector<int> rblockpsum;
    int numfin;
    int totsz;
    int len;
    dat(){
        numfin = 0;
        totsz = 0;
        len = 0;
    }
    dat(int num){
        numfin = 1;
        totsz = num;
        len = 1;
        lblockpos.push_back(0);
        lblocknum.push_back(0);
        lblockvals.push_back(num);
        lblockpsum.push_back(num);
        rblockpos.push_back(0);
        rblocknum.push_back(0);
        rblockvals.push_back(num);
        rblockpsum.push_back(num);
    }
};

dat mer(dat a, dat b){
    //printf("mer %d and %d\n",a.numfin,b.numfin);
    dat ans = dat();
    ans.totsz = a.totsz+b.totsz;
    ans.len = a.len+b.len;
    for (int x = 0; x<a.lblocknum.size(); x++){
        ans.lblocknum.push_back(a.lblocknum[x]);
        ans.lblockpos.push_back(a.lblockpos[x]);
        ans.lblockvals.push_back(a.lblockvals[x]);
        ans.lblockpsum.push_back(a.lblockpsum[x]);
        //printf("lblock %d %d %d %d\n",a.lblocknum[x],a.lblockpos[x],a.lblockvals[x],a.lblockpsum[x]);
    }
    for (int x = 0; x<b.rblocknum.size(); x++){
        ans.rblocknum.push_back(b.rblocknum[x]);
        ans.rblockpos.push_back(b.rblockpos[x]);
        ans.rblockvals.push_back(b.rblockvals[x]);
        ans.rblockpsum.push_back(b.rblockpsum[x]);
        //printf("rblock %d %d %d %d\n",b.rblocknum[x],b.rblockpos[x],b.rblockvals[x],b.rblockpsum[x]);
    }
    //printf("hi\n");
    int t1 = a.totsz;
    int li,ri;
    bool canfin = true;
    for (int x = 0; x<b.lblocknum.size(); x++){
        if (b.lblockvals[x]<=t1){
            t1 += b.lblockpsum[x];
            if (t1>INF) t1 = INF;
        }
        else{
            li = ans.lblocknum.size();
            canfin = false;
            //assert(!ans.lblockpsum.empty());
            ans.lblockpsum.back() += t1-a.totsz;
            ans.lblockpos.push_back(b.lblockpos[x]+a.len);
            ans.lblocknum.push_back(a.numfin);
            ans.lblockvals.push_back(b.lblockvals[x]);
            ans.lblockpsum.push_back(b.totsz-(t1-a.totsz));
            break;
        }
    }
    if (canfin){
        ans.lblockpsum.back() += b.totsz;
        ans.numfin += a.numfin;
    }
    t1 = b.totsz;
    canfin = true;
    for (int x = 0; x<a.rblocknum.size(); x++){
        if (a.rblockvals[x]<=t1){
            t1 += a.rblockpsum[x];
            if (t1>INF) t1 = INF;
        }
        else{
            ri = ans.rblocknum.size();
            canfin = false;
            //assert(!ans.rblockpsum.empty());
            ans.rblockpsum.back() += t1-b.totsz;
            ans.rblockpos.push_back(a.rblockpos[x]+b.len);
            ans.rblocknum.push_back(b.numfin);
            ans.rblockvals.push_back(a.rblockvals[x]);
            ans.rblockpsum.push_back(a.totsz-(t1-b.totsz));
            break;
        }
    }
    if (canfin){
        ans.rblockpsum.back() += a.totsz;
        ans.numfin += b.numfin;
    }
    //printf("hi\n");
    t1 = 0;
    int t2 = 0;
    int maxv = 0;
    long long sum1 = 0;
    for (int x = 0; x<a.rblocknum.size(); x++){
        sum1+= a.rblockpsum[x];
    }
    for (int x = 1; x<a.rblocknum.size(); x++){
        //printf("arblock %d %d %d %d\n",a.rblocknum[x],a.rblockpos[x],a.rblockvals[x],a.rblockpsum[x]);
        t1 += a.rblocknum[x];
        t2 += a.rblockpsum[x-1];
        sum1 -= a.rblockpsum[x-1];
        t2 = min(t2,INF);
        bool added = false;
        while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
            t2 += b.lblockpsum[maxv];
            t2 = min(t2,INF);
            maxv++;
            added = true;
        }
        if (a.rblockvals[x]>t2){
            if (maxv==b.lblocknum.size()){
                if (ans.rblockpos.back()==b.len+a.rblockpos[x]){
                    ans.rblocknum.back()+=t1;
                }
                else{
                    ans.rblockpsum.back() -= sum1;
                    ans.rblockpos.push_back(b.len+a.rblockpos[x]);
                    ans.rblocknum.push_back(t1);
                    ans.rblockvals.push_back(a.rblockvals[x]);
                    ans.rblockpsum.push_back(sum1);
                }
            }
            t1 = 0;
        }
    }
    t2 += a.rblockpsum.back();
    while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
        t2 += b.lblockpsum[maxv];
        t2 = min(t2,INF);
        maxv++;
    }
    //printf("maxv = %d\n",maxv);
    if (maxv==b.lblocknum.size()){
        ans.numfin += t1;
    }
    else{
        ans.lblocknum[li] += t1;
    }
    t1 = 0;
    t2 = 0;
    maxv = 0;
    int sum2 = 0;
    for (int x = 0; x<b.lblocknum.size(); x++){
        sum2 += b.lblockpsum[x];
    }
    for (int x = 1; x<b.lblocknum.size(); x++){
        //printf("blblock %d %d %d %d\n",b.lblocknum[x],b.lblockpos[x],b.lblockvals[x],b.lblockpsum[x]);
        t1 += b.lblocknum[x];
        t2 += b.lblockpsum[x-1];
        sum2 -= b.lblockpsum[x-1];
        t2 = min(t2,INF);
        bool added = false;
        while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
            t2 += a.rblockpsum[maxv];
            t2 = min(t2,INF);
            maxv++;
            added = true;
        }
        if (b.lblockvals[x]>t2){
            if (maxv==a.rblocknum.size()){
                if (ans.lblockpos.back()==a.len+b.lblockpos[x]){
                    ans.lblocknum.back()+=t1;
                }
                else{
                    ans.lblockpsum.back() -= sum2;
                    ans.lblockpos.push_back(a.len+b.lblockpos[x]);
                    ans.lblocknum.push_back(t1);
                    ans.lblockvals.push_back(b.lblockvals[x]);
                    ans.lblockpsum.push_back(sum2);
                }
            }
            t1 = 0;
        }
    }
    t2 += b.lblockpsum.back();
    while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
        t2 += a.rblockpsum[maxv];
        t2 = min(t2,INF);
        maxv++;
    }
    if (maxv==a.rblocknum.size()){
        ans.numfin += t1;
    }
    else{
        ans.rblocknum[ri] += t1;
    }
    assert(ans.lblocknum.size()==ans.lblockpos.size());
    assert(ans.lblockpos.size()==ans.lblockvals.size());
    assert(ans.lblockpsum.size()==ans.lblockvals.size());
    return ans;
}

int arr[100005];

struct node{
    int s,e;
    dat v;
    node *l,*r;
    node (int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            v = dat(arr[s]);
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            v = mer(l->v,r->v);
        //printf("node %d to %d has numfin %d\n",s,e,v.numfin);
        }
    }
    dat qu(int a, int b){
        //printf("node %d to %d, %d %d\n",s,e,a,b);
        if (a<=s && e<=b){
            return v;
        }
        if (b<=(s+e)/2){
            return l->qu(a,b);
        }
        if (a>(s+e)/2){
            return r->qu(a,b);
        }
        //printf("end %d %d\n",s,e);
        return mer(l->qu(a,b),r->qu(a,b));
    }
    void upd(int pos){
        if (s==e){
            v = dat(arr[s]);
            return;
        }
        if (pos<=(s+e)/2){
            l->upd(pos);
        }
        else{
            r->upd(pos);
        }
        v = mer(l->v,r->v);
    }
}*root;

 main(){
    int n;
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        scanf("%lld",&arr[x]);
    }
    root = new node(1,n);
    int q;
    scanf("%lld",&q);
    while (q--){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        if (a==1){
            arr[b] = c;
            root->upd(b);
        }
        else{
            printf("%lld\n",root->qu(b,c).numfin);
        }
    }
}

Compilation message

fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int x = 0; x<a.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int x = 0; x<b.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int x = 0; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:85:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int x = 0; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:111:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int x = 0; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:114:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int x = 1; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:121:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
      |                ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:128:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             if (maxv==b.lblocknum.size()){
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:120:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
  120 |         bool added = false;
      |              ^~~~~
fish2.cpp:144:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:150:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     if (maxv==b.lblocknum.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:160:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int x = 0; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:163:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int x = 1; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:170:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
      |                ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:177:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             if (maxv==a.rblocknum.size()){
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:169:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
  169 |         bool added = false;
      |              ^~~~~
fish2.cpp:193:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:198:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     if (maxv==a.rblocknum.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp: At global scope:
fish2.cpp:258:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  258 |  main(){
      |  ^~~~
fish2.cpp: In function 'int main()':
fish2.cpp:260:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
fish2.cpp:262:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         scanf("%lld",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:266:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
fish2.cpp:269:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:202:25: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
  202 |         ans.rblocknum[ri] += t1;
      |                         ^
fish2.cpp:154:25: warning: 'li' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |         ans.lblocknum[li] += t1;
      |                         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 7 ms 872 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 11 ms 864 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 9 ms 852 KB Output is correct
15 Correct 8 ms 852 KB Output is correct
16 Correct 9 ms 852 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 7 ms 852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 195 ms 113496 KB Output is correct
3 Correct 196 ms 110636 KB Output is correct
4 Correct 209 ms 114020 KB Output is correct
5 Correct 187 ms 111052 KB Output is correct
6 Correct 171 ms 102908 KB Output is correct
7 Correct 173 ms 102776 KB Output is correct
8 Correct 171 ms 102924 KB Output is correct
9 Correct 177 ms 102780 KB Output is correct
10 Correct 232 ms 115364 KB Output is correct
11 Correct 191 ms 108748 KB Output is correct
12 Correct 175 ms 102116 KB Output is correct
13 Correct 179 ms 102040 KB Output is correct
14 Correct 174 ms 103304 KB Output is correct
15 Correct 195 ms 104128 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 7 ms 872 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 11 ms 864 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 9 ms 852 KB Output is correct
15 Correct 8 ms 852 KB Output is correct
16 Correct 9 ms 852 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 7 ms 852 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 195 ms 113496 KB Output is correct
23 Correct 196 ms 110636 KB Output is correct
24 Correct 209 ms 114020 KB Output is correct
25 Correct 187 ms 111052 KB Output is correct
26 Correct 171 ms 102908 KB Output is correct
27 Correct 173 ms 102776 KB Output is correct
28 Correct 171 ms 102924 KB Output is correct
29 Correct 177 ms 102780 KB Output is correct
30 Correct 232 ms 115364 KB Output is correct
31 Correct 191 ms 108748 KB Output is correct
32 Correct 175 ms 102116 KB Output is correct
33 Correct 179 ms 102040 KB Output is correct
34 Correct 174 ms 103304 KB Output is correct
35 Correct 195 ms 104128 KB Output is correct
36 Correct 238 ms 114308 KB Output is correct
37 Correct 222 ms 110796 KB Output is correct
38 Correct 221 ms 110752 KB Output is correct
39 Correct 228 ms 114084 KB Output is correct
40 Correct 218 ms 110712 KB Output is correct
41 Correct 207 ms 103052 KB Output is correct
42 Correct 202 ms 103096 KB Output is correct
43 Correct 197 ms 102932 KB Output is correct
44 Correct 203 ms 102768 KB Output is correct
45 Correct 247 ms 115672 KB Output is correct
46 Correct 220 ms 115660 KB Output is correct
47 Correct 289 ms 107940 KB Output is correct
48 Correct 187 ms 102448 KB Output is correct
49 Correct 177 ms 102136 KB Output is correct
50 Correct 204 ms 103400 KB Output is correct
51 Correct 223 ms 104104 KB Output is correct
52 Correct 199 ms 103324 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 195 ms 113496 KB Output is correct
3 Correct 196 ms 110636 KB Output is correct
4 Correct 209 ms 114020 KB Output is correct
5 Correct 187 ms 111052 KB Output is correct
6 Correct 171 ms 102908 KB Output is correct
7 Correct 173 ms 102776 KB Output is correct
8 Correct 171 ms 102924 KB Output is correct
9 Correct 177 ms 102780 KB Output is correct
10 Correct 232 ms 115364 KB Output is correct
11 Correct 191 ms 108748 KB Output is correct
12 Correct 175 ms 102116 KB Output is correct
13 Correct 179 ms 102040 KB Output is correct
14 Correct 174 ms 103304 KB Output is correct
15 Correct 195 ms 104128 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2788 ms 112792 KB Output is correct
18 Correct 2581 ms 116144 KB Output is correct
19 Correct 2771 ms 112736 KB Output is correct
20 Correct 2899 ms 112628 KB Output is correct
21 Correct 2801 ms 112388 KB Output is correct
22 Correct 2428 ms 115964 KB Output is correct
23 Correct 2745 ms 112104 KB Output is correct
24 Correct 2754 ms 112432 KB Output is correct
25 Correct 2706 ms 112508 KB Output is correct
26 Correct 2892 ms 112472 KB Output is correct
27 Correct 1550 ms 105060 KB Output is correct
28 Correct 1548 ms 104848 KB Output is correct
29 Correct 1601 ms 104928 KB Output is correct
30 Correct 2004 ms 104260 KB Output is correct
31 Correct 2161 ms 104544 KB Output is correct
32 Correct 3410 ms 110012 KB Output is correct
33 Correct 3414 ms 117372 KB Output is correct
34 Correct 3199 ms 110096 KB Output is correct
35 Correct 2861 ms 109416 KB Output is correct
36 Correct 3279 ms 117532 KB Output is correct
37 Correct 1563 ms 103872 KB Output is correct
38 Correct 1502 ms 103708 KB Output is correct
39 Correct 1795 ms 105424 KB Output is correct
40 Correct 2019 ms 106148 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 195 ms 113496 KB Output is correct
3 Correct 196 ms 110636 KB Output is correct
4 Correct 209 ms 114020 KB Output is correct
5 Correct 187 ms 111052 KB Output is correct
6 Correct 171 ms 102908 KB Output is correct
7 Correct 173 ms 102776 KB Output is correct
8 Correct 171 ms 102924 KB Output is correct
9 Correct 177 ms 102780 KB Output is correct
10 Correct 232 ms 115364 KB Output is correct
11 Correct 191 ms 108748 KB Output is correct
12 Correct 175 ms 102116 KB Output is correct
13 Correct 179 ms 102040 KB Output is correct
14 Correct 174 ms 103304 KB Output is correct
15 Correct 195 ms 104128 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 3554 ms 115376 KB Output is correct
18 Correct 3288 ms 112896 KB Output is correct
19 Correct 2459 ms 112020 KB Output is correct
20 Correct 2342 ms 112900 KB Output is correct
21 Correct 2978 ms 115192 KB Output is correct
22 Correct 3321 ms 112940 KB Output is correct
23 Correct 3070 ms 111776 KB Output is correct
24 Correct 3027 ms 112896 KB Output is correct
25 Correct 2667 ms 111900 KB Output is correct
26 Correct 1839 ms 104784 KB Output is correct
27 Correct 2728 ms 105004 KB Output is correct
28 Correct 2253 ms 107160 KB Output is correct
29 Correct 2145 ms 104956 KB Output is correct
30 Correct 2694 ms 104684 KB Output is correct
31 Correct 2838 ms 106892 KB Output is correct
32 Correct 3208 ms 110840 KB Output is correct
33 Correct 2275 ms 109920 KB Output is correct
34 Correct 2986 ms 117180 KB Output is correct
35 Correct 2139 ms 117008 KB Output is correct
36 Correct 2560 ms 110164 KB Output is correct
37 Correct 2625 ms 107904 KB Output is correct
38 Correct 1598 ms 107424 KB Output is correct
39 Correct 2019 ms 105868 KB Output is correct
40 Correct 774 ms 105804 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 7 ms 872 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 11 ms 864 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 9 ms 852 KB Output is correct
15 Correct 8 ms 852 KB Output is correct
16 Correct 9 ms 852 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 7 ms 852 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 195 ms 113496 KB Output is correct
23 Correct 196 ms 110636 KB Output is correct
24 Correct 209 ms 114020 KB Output is correct
25 Correct 187 ms 111052 KB Output is correct
26 Correct 171 ms 102908 KB Output is correct
27 Correct 173 ms 102776 KB Output is correct
28 Correct 171 ms 102924 KB Output is correct
29 Correct 177 ms 102780 KB Output is correct
30 Correct 232 ms 115364 KB Output is correct
31 Correct 191 ms 108748 KB Output is correct
32 Correct 175 ms 102116 KB Output is correct
33 Correct 179 ms 102040 KB Output is correct
34 Correct 174 ms 103304 KB Output is correct
35 Correct 195 ms 104128 KB Output is correct
36 Correct 238 ms 114308 KB Output is correct
37 Correct 222 ms 110796 KB Output is correct
38 Correct 221 ms 110752 KB Output is correct
39 Correct 228 ms 114084 KB Output is correct
40 Correct 218 ms 110712 KB Output is correct
41 Correct 207 ms 103052 KB Output is correct
42 Correct 202 ms 103096 KB Output is correct
43 Correct 197 ms 102932 KB Output is correct
44 Correct 203 ms 102768 KB Output is correct
45 Correct 247 ms 115672 KB Output is correct
46 Correct 220 ms 115660 KB Output is correct
47 Correct 289 ms 107940 KB Output is correct
48 Correct 187 ms 102448 KB Output is correct
49 Correct 177 ms 102136 KB Output is correct
50 Correct 204 ms 103400 KB Output is correct
51 Correct 223 ms 104104 KB Output is correct
52 Correct 199 ms 103324 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 2788 ms 112792 KB Output is correct
55 Correct 2581 ms 116144 KB Output is correct
56 Correct 2771 ms 112736 KB Output is correct
57 Correct 2899 ms 112628 KB Output is correct
58 Correct 2801 ms 112388 KB Output is correct
59 Correct 2428 ms 115964 KB Output is correct
60 Correct 2745 ms 112104 KB Output is correct
61 Correct 2754 ms 112432 KB Output is correct
62 Correct 2706 ms 112508 KB Output is correct
63 Correct 2892 ms 112472 KB Output is correct
64 Correct 1550 ms 105060 KB Output is correct
65 Correct 1548 ms 104848 KB Output is correct
66 Correct 1601 ms 104928 KB Output is correct
67 Correct 2004 ms 104260 KB Output is correct
68 Correct 2161 ms 104544 KB Output is correct
69 Correct 3410 ms 110012 KB Output is correct
70 Correct 3414 ms 117372 KB Output is correct
71 Correct 3199 ms 110096 KB Output is correct
72 Correct 2861 ms 109416 KB Output is correct
73 Correct 3279 ms 117532 KB Output is correct
74 Correct 1563 ms 103872 KB Output is correct
75 Correct 1502 ms 103708 KB Output is correct
76 Correct 1795 ms 105424 KB Output is correct
77 Correct 2019 ms 106148 KB Output is correct
78 Correct 1 ms 212 KB Output is correct
79 Correct 3554 ms 115376 KB Output is correct
80 Correct 3288 ms 112896 KB Output is correct
81 Correct 2459 ms 112020 KB Output is correct
82 Correct 2342 ms 112900 KB Output is correct
83 Correct 2978 ms 115192 KB Output is correct
84 Correct 3321 ms 112940 KB Output is correct
85 Correct 3070 ms 111776 KB Output is correct
86 Correct 3027 ms 112896 KB Output is correct
87 Correct 2667 ms 111900 KB Output is correct
88 Correct 1839 ms 104784 KB Output is correct
89 Correct 2728 ms 105004 KB Output is correct
90 Correct 2253 ms 107160 KB Output is correct
91 Correct 2145 ms 104956 KB Output is correct
92 Correct 2694 ms 104684 KB Output is correct
93 Correct 2838 ms 106892 KB Output is correct
94 Correct 3208 ms 110840 KB Output is correct
95 Correct 2275 ms 109920 KB Output is correct
96 Correct 2986 ms 117180 KB Output is correct
97 Correct 2139 ms 117008 KB Output is correct
98 Correct 2560 ms 110164 KB Output is correct
99 Correct 2625 ms 107904 KB Output is correct
100 Correct 1598 ms 107424 KB Output is correct
101 Correct 2019 ms 105868 KB Output is correct
102 Correct 774 ms 105804 KB Output is correct
103 Correct 3941 ms 112072 KB Output is correct
104 Correct 3493 ms 115928 KB Output is correct
105 Correct 2919 ms 112712 KB Output is correct
106 Correct 2719 ms 112808 KB Output is correct
107 Correct 3611 ms 112164 KB Output is correct
108 Correct 3428 ms 115876 KB Output is correct
109 Correct 3021 ms 112388 KB Output is correct
110 Correct 2947 ms 112676 KB Output is correct
111 Correct 2993 ms 112536 KB Output is correct
112 Correct 2760 ms 112452 KB Output is correct
113 Correct 2563 ms 104964 KB Output is correct
114 Correct 1733 ms 104956 KB Output is correct
115 Correct 3207 ms 107168 KB Output is correct
116 Correct 2936 ms 107360 KB Output is correct
117 Correct 1817 ms 104936 KB Output is correct
118 Correct 2306 ms 106592 KB Output is correct
119 Correct 2753 ms 104908 KB Output is correct
120 Correct 2960 ms 107136 KB Output is correct
121 Correct 2574 ms 107516 KB Output is correct
122 Correct 3236 ms 110636 KB Output is correct
123 Correct 2805 ms 110212 KB Output is correct
124 Correct 2593 ms 109360 KB Output is correct
125 Correct 2586 ms 107564 KB Output is correct
126 Correct 2596 ms 107928 KB Output is correct
127 Correct 3063 ms 106784 KB Output is correct
128 Correct 2051 ms 105840 KB Output is correct
129 Correct 2570 ms 106324 KB Output is correct
130 Correct 2210 ms 106076 KB Output is correct