oj.uz

Submission #958352

# Submission time Handle Problem Language Result Execution time Memory
958352 2024-04-05T13:42:30 Z shenfe1 Food Court (JOI21_foodcourt) C++17
100 / 100
 679 ms 117272 KB 
#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")
#pragma optimize("unroll-loops")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
#define int ll
#define ull unsigned ll

const int MAX=3e5+10;
const int B=331;
const int maxB=1000;
const int N=104;
const int block=450;
const int inf=1e18;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct segtree{
  int t[3][4*MAX],op[3][4*MAX];

  void init(){
    mem(t,0);
    mem(op,0);
  }

  void upd(int v,int o,int x){
    if(op[2][v]==o){
      t[2][v]+=x;
      return;
    }
    if(op[2][v]==1){
      if(t[2][v]>=x){
        t[2][v]-=x;
      }
      else{
        op[2][v]=(op[2][v]^1);
        t[2][v]=x-t[2][v];
      }
      return;
    }
    if(op[1][v]==op[2][v]){
      t[1][v]+=t[2][v];
    }
    else{
      if(t[1][v]>=t[2][v]){
        t[1][v]-=t[2][v];
      }
      else{
        op[1][v]=(op[1][v]^1);
        t[1][v]=t[2][v]-t[1][v];
      }
    }
    t[2][v]=x;
    op[2][v]=o;
  }

  void push(int v){
    for(int i=1;i<=2;i++){
      upd(2*v,op[i][v],t[i][v]);
      upd(2*v+1,op[i][v],t[i][v]);
      op[i][v]=t[i][v]=0;
    }
  }

  void update(int v,int tl,int tr,int l,int r,int o,int x){
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      upd(v,o,x);
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,o,x);
    update(2*v+1,tm+1,tr,l,r,o,x);
  }

  int get(int v,int tl,int tr,int pos){
    if(tl==tr){
      int ans=0;
      for(int i=1;i<=2;i++){
        if(op[i][v]==0)ans-=t[i][v];
        else ans+=t[i][v];
        ans=max(ans,0ll);
      }
      return ans;
    }
    push(v);
    int tm=(tl+tr)/2;
    if(pos<=tm)return get(2*v,tl,tm,pos);
    else return get(2*v+1,tm+1,tr,pos);
  }
}t;

int n,m,q;
int del[MAX];
int type[MAX];
int l[MAX],r[MAX],c[MAX],x[MAX];
vector<pii> zap[MAX];
int ans[MAX];

struct segtree1{
  pii t[4*MAX];
  int add[4*MAX];

  void build(int v,int tl,int tr){
    if(tl==tr){
      t[v].S=tl;
      return;
    }
    int tm=(tl+tr)/2;
    build(2*v,tl,tm);
    build(2*v+1,tm+1,tr);
    t[v]=max(t[2*v],t[2*v+1]);
  }

  void init(){
    mem(t,0);
    mem(add,0);
    build(1,1,n);
  }

  void push(int v){
    add[2*v]+=add[v];
    add[2*v+1]+=add[v];
    t[2*v].F+=add[v];
    t[2*v+1].F+=add[v];
    add[v]=0;
  }

  pii get(int v,int tl,int tr,int l,int r){
    if(l>r||tl>r||l>tr)return {-inf,-inf};
    if(l<=tl&&tr<=r)return t[v];
    push(v);
    int tm=(tl+tr)/2;
    return max(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
  }

  void update(int v,int tl,int tr,int l,int r,int x){
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      t[v].F+=x;
      add[v]+=x;
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,x);
    update(2*v+1,tm+1,tr,l,r,x);
    t[v]=max(t[2*v],t[2*v+1]);
  }

}t1;


void solve(){
  cin>>n>>m>>q;
  mem(ans,-1);
  t.init();
  t1.init();
  for(int i=1;i<=q;i++){
    cin>>type[i];
    if(type[i]==1){
      cin>>l[i]>>r[i]>>c[i]>>x[i];
      t1.update(1,1,n,l[i],r[i],x[i]);
      t.update(1,1,n,l[i],r[i],1,x[i]);
    }
    else if(type[i]==2){
      cin>>l[i]>>r[i]>>x[i];
      t.update(1,1,n,l[i],r[i],0,x[i]);
    }
    else{
      cin>>l[i]>>r[i];
      // cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<t1.get(1,1,n,l[i],l[i]).F<<" "<<t.get(1,1,n,l[i])<<"\n";
      r[i]+=t1.get(1,1,n,l[i],l[i]).F-t.get(1,1,n,l[i]);
      zap[l[i]].pb({r[i],i});
      // cout<<l[i]<<" "<<r[i]<<"\n";
    }
  }
  t1.init();
  for(int i=1;i<=n;i++){
    sort(all(zap[i]));
    reverse(all(zap[i]));
    // cout<<i<<"\n";
    // for(auto x:zap[i]){
    //   cout<<x.F<<" "<<x.S<<"\n";
    // }
    if(!zap[i].empty())t1.update(1,1,n,i,i,-zap[i].back().F);
    else t1.update(1,1,n,i,i,-inf);
  }
  // for(int i=1;i<=n;i++){
  //   cout<<t1.get(1,1,n,i,i).F<<" ";
  // }
  // cout<<"\n";
  for(int i=1;i<=q;i++){
    if(type[i]==1){
      t1.update(1,1,n,l[i],r[i],x[i]);
    }
    while(t1.get(1,1,n,1,n).F>=0){
      int pos=t1.get(1,1,n,1,n).S;
      // cout<<pos<<" "<<i<<" "<<zap[pos].back().S<<" "<<t1.get(1,1,n,1,n).F<<"\n";
      if(zap[pos].back().S>i)ans[zap[pos].back().S]=c[i];
      else ans[zap[pos].back().S]=0;
      if(sz(zap[pos])>1){
        t1.update(1,1,n,pos,pos,zap[pos].back().F-zap[pos][sz(zap[pos])-2].F);
      }
      else{
        t1.update(1,1,n,pos,pos,-inf);
      }
      zap[pos].ppb();
    }
  }
  for(int i=1;i<=n;i++){
    while(!zap[i].empty()){
      ans[zap[i].back().S]=0;
      zap[i].ppb();
    }
  }
  for(int i=1;i<=q;i++){
    if(ans[i]!=-1)cout<<ans[i]<<"\n";
  }
}

signed main(){
  // freopen("triangles.in","r",stdin);
  // freopen("triangles.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--)solve();
}

Compilation message

foodcourt.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
foodcourt.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      | 
foodcourt.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("unroll-loops")
      | 
foodcourt.cpp: In member function 'void segtree1::init()':
foodcourt.cpp:17:38: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   17 | #define mem(a,i) memset(a,i,sizeof(a))
      |                                      ^
foodcourt.cpp:149:5: note: in expansion of macro 'mem'
  149 |     mem(t,0);
      |     ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 102228 KB Output is correct
2 Correct 20 ms 102236 KB Output is correct
3 Correct 21 ms 102232 KB Output is correct
4 Correct 20 ms 102236 KB Output is correct
5 Correct 19 ms 102232 KB Output is correct
6 Correct 18 ms 102236 KB Output is correct
7 Correct 21 ms 102232 KB Output is correct
8 Correct 21 ms 102232 KB Output is correct
9 Correct 21 ms 102236 KB Output is correct
10 Correct 21 ms 102348 KB Output is correct
11 Correct 20 ms 102232 KB Output is correct
12 Correct 23 ms 102736 KB Output is correct
13 Correct 19 ms 102368 KB Output is correct
14 Correct 19 ms 102136 KB Output is correct
15 Correct 20 ms 102236 KB Output is correct
16 Correct 20 ms 102236 KB Output is correct
17 Correct 21 ms 102388 KB Output is correct
18 Correct 20 ms 102236 KB Output is correct
19 Correct 20 ms 102344 KB Output is correct
20 Correct 20 ms 102232 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 102228 KB Output is correct
2 Correct 20 ms 102236 KB Output is correct
3 Correct 21 ms 102232 KB Output is correct
4 Correct 20 ms 102236 KB Output is correct
5 Correct 19 ms 102232 KB Output is correct
6 Correct 18 ms 102236 KB Output is correct
7 Correct 21 ms 102232 KB Output is correct
8 Correct 21 ms 102232 KB Output is correct
9 Correct 21 ms 102236 KB Output is correct
10 Correct 21 ms 102348 KB Output is correct
11 Correct 20 ms 102232 KB Output is correct
12 Correct 23 ms 102736 KB Output is correct
13 Correct 19 ms 102368 KB Output is correct
14 Correct 19 ms 102136 KB Output is correct
15 Correct 20 ms 102236 KB Output is correct
16 Correct 20 ms 102236 KB Output is correct
17 Correct 21 ms 102388 KB Output is correct
18 Correct 20 ms 102236 KB Output is correct
19 Correct 20 ms 102344 KB Output is correct
20 Correct 20 ms 102232 KB Output is correct
21 Correct 20 ms 102236 KB Output is correct
22 Correct 23 ms 102236 KB Output is correct
23 Correct 21 ms 102588 KB Output is correct
24 Correct 21 ms 102340 KB Output is correct
25 Correct 18 ms 102232 KB Output is correct
26 Correct 19 ms 104284 KB Output is correct
27 Correct 21 ms 102272 KB Output is correct
28 Correct 20 ms 102232 KB Output is correct
29 Correct 21 ms 104284 KB Output is correct
30 Correct 21 ms 102236 KB Output is correct
31 Correct 21 ms 104284 KB Output is correct
32 Correct 20 ms 102236 KB Output is correct
33 Correct 21 ms 102172 KB Output is correct
34 Correct 20 ms 104284 KB Output is correct
35 Correct 21 ms 102236 KB Output is correct
36 Correct 21 ms 102360 KB Output is correct
37 Correct 19 ms 102236 KB Output is correct
38 Correct 20 ms 102236 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 103760 KB Output is correct
2 Correct 94 ms 103256 KB Output is correct
3 Correct 96 ms 103424 KB Output is correct
4 Correct 95 ms 103508 KB Output is correct
5 Correct 97 ms 103252 KB Output is correct
6 Correct 105 ms 103380 KB Output is correct
7 Correct 32 ms 105180 KB Output is correct
8 Correct 34 ms 105244 KB Output is correct
9 Correct 89 ms 103188 KB Output is correct
10 Correct 92 ms 103420 KB Output is correct
11 Correct 90 ms 103340 KB Output is correct
12 Correct 99 ms 103244 KB Output is correct
13 Correct 85 ms 103300 KB Output is correct
14 Correct 97 ms 103480 KB Output is correct
15 Correct 107 ms 103252 KB Output is correct
16 Correct 103 ms 103248 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 107484 KB Output is correct
2 Correct 417 ms 110676 KB Output is correct
3 Correct 601 ms 114000 KB Output is correct
4 Correct 467 ms 110420 KB Output is correct
5 Correct 426 ms 110520 KB Output is correct
6 Correct 633 ms 113604 KB Output is correct
7 Correct 83 ms 111620 KB Output is correct
8 Correct 89 ms 111140 KB Output is correct
9 Correct 654 ms 115100 KB Output is correct
10 Correct 658 ms 115212 KB Output is correct
11 Correct 537 ms 113304 KB Output is correct
12 Correct 555 ms 113744 KB Output is correct
13 Correct 535 ms 112980 KB Output is correct
14 Correct 571 ms 113488 KB Output is correct
15 Correct 588 ms 113532 KB Output is correct
16 Correct 600 ms 113408 KB Output is correct
17 Correct 609 ms 114260 KB Output is correct
18 Correct 592 ms 114584 KB Output is correct
19 Correct 621 ms 114404 KB Output is correct
20 Correct 590 ms 114408 KB Output is correct
21 Correct 639 ms 114288 KB Output is correct
22 Correct 634 ms 114276 KB Output is correct
23 Correct 658 ms 114252 KB Output is correct
24 Correct 623 ms 114272 KB Output is correct
25 Correct 462 ms 114260 KB Output is correct
26 Correct 518 ms 114552 KB Output is correct
27 Correct 444 ms 113500 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 102228 KB Output is correct
2 Correct 20 ms 102236 KB Output is correct
3 Correct 21 ms 102232 KB Output is correct
4 Correct 20 ms 102236 KB Output is correct
5 Correct 19 ms 102232 KB Output is correct
6 Correct 18 ms 102236 KB Output is correct
7 Correct 21 ms 102232 KB Output is correct
8 Correct 21 ms 102232 KB Output is correct
9 Correct 21 ms 102236 KB Output is correct
10 Correct 21 ms 102348 KB Output is correct
11 Correct 20 ms 102232 KB Output is correct
12 Correct 23 ms 102736 KB Output is correct
13 Correct 19 ms 102368 KB Output is correct
14 Correct 19 ms 102136 KB Output is correct
15 Correct 20 ms 102236 KB Output is correct
16 Correct 20 ms 102236 KB Output is correct
17 Correct 21 ms 102388 KB Output is correct
18 Correct 20 ms 102236 KB Output is correct
19 Correct 20 ms 102344 KB Output is correct
20 Correct 20 ms 102232 KB Output is correct
21 Correct 101 ms 103760 KB Output is correct
22 Correct 94 ms 103256 KB Output is correct
23 Correct 96 ms 103424 KB Output is correct
24 Correct 95 ms 103508 KB Output is correct
25 Correct 97 ms 103252 KB Output is correct
26 Correct 105 ms 103380 KB Output is correct
27 Correct 32 ms 105180 KB Output is correct
28 Correct 34 ms 105244 KB Output is correct
29 Correct 89 ms 103188 KB Output is correct
30 Correct 92 ms 103420 KB Output is correct
31 Correct 90 ms 103340 KB Output is correct
32 Correct 99 ms 103244 KB Output is correct
33 Correct 85 ms 103300 KB Output is correct
34 Correct 97 ms 103480 KB Output is correct
35 Correct 107 ms 103252 KB Output is correct
36 Correct 103 ms 103248 KB Output is correct
37 Correct 117 ms 107784 KB Output is correct
38 Correct 107 ms 107548 KB Output is correct
39 Correct 35 ms 107224 KB Output is correct
40 Correct 33 ms 107344 KB Output is correct
41 Correct 128 ms 107856 KB Output is correct
42 Correct 122 ms 107564 KB Output is correct
43 Correct 130 ms 107568 KB Output is correct
44 Correct 122 ms 107556 KB Output is correct
45 Correct 135 ms 107656 KB Output is correct
46 Correct 132 ms 107600 KB Output is correct
47 Correct 68 ms 107856 KB Output is correct
48 Correct 128 ms 108068 KB Output is correct
49 Correct 93 ms 105100 KB Output is correct
50 Correct 114 ms 107580 KB Output is correct
51 Correct 130 ms 107604 KB Output is correct
52 Correct 142 ms 107604 KB Output is correct
53 Correct 88 ms 107344 KB Output is correct
54 Correct 106 ms 107604 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 108368 KB Output is correct
2 Correct 136 ms 108880 KB Output is correct
3 Correct 137 ms 109140 KB Output is correct
4 Correct 104 ms 106224 KB Output is correct
5 Correct 118 ms 108736 KB Output is correct
6 Correct 141 ms 108980 KB Output is correct
7 Correct 37 ms 108240 KB Output is correct
8 Correct 36 ms 108092 KB Output is correct
9 Correct 88 ms 109024 KB Output is correct
10 Correct 96 ms 106064 KB Output is correct
11 Correct 127 ms 109032 KB Output is correct
12 Correct 128 ms 108936 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 102228 KB Output is correct
2 Correct 20 ms 102236 KB Output is correct
3 Correct 21 ms 102232 KB Output is correct
4 Correct 20 ms 102236 KB Output is correct
5 Correct 19 ms 102232 KB Output is correct
6 Correct 18 ms 102236 KB Output is correct
7 Correct 21 ms 102232 KB Output is correct
8 Correct 21 ms 102232 KB Output is correct
9 Correct 21 ms 102236 KB Output is correct
10 Correct 21 ms 102348 KB Output is correct
11 Correct 20 ms 102232 KB Output is correct
12 Correct 23 ms 102736 KB Output is correct
13 Correct 19 ms 102368 KB Output is correct
14 Correct 19 ms 102136 KB Output is correct
15 Correct 20 ms 102236 KB Output is correct
16 Correct 20 ms 102236 KB Output is correct
17 Correct 21 ms 102388 KB Output is correct
18 Correct 20 ms 102236 KB Output is correct
19 Correct 20 ms 102344 KB Output is correct
20 Correct 20 ms 102232 KB Output is correct
21 Correct 20 ms 102236 KB Output is correct
22 Correct 23 ms 102236 KB Output is correct
23 Correct 21 ms 102588 KB Output is correct
24 Correct 21 ms 102340 KB Output is correct
25 Correct 18 ms 102232 KB Output is correct
26 Correct 19 ms 104284 KB Output is correct
27 Correct 21 ms 102272 KB Output is correct
28 Correct 20 ms 102232 KB Output is correct
29 Correct 21 ms 104284 KB Output is correct
30 Correct 21 ms 102236 KB Output is correct
31 Correct 21 ms 104284 KB Output is correct
32 Correct 20 ms 102236 KB Output is correct
33 Correct 21 ms 102172 KB Output is correct
34 Correct 20 ms 104284 KB Output is correct
35 Correct 21 ms 102236 KB Output is correct
36 Correct 21 ms 102360 KB Output is correct
37 Correct 19 ms 102236 KB Output is correct
38 Correct 20 ms 102236 KB Output is correct
39 Correct 101 ms 103760 KB Output is correct
40 Correct 94 ms 103256 KB Output is correct
41 Correct 96 ms 103424 KB Output is correct
42 Correct 95 ms 103508 KB Output is correct
43 Correct 97 ms 103252 KB Output is correct
44 Correct 105 ms 103380 KB Output is correct
45 Correct 32 ms 105180 KB Output is correct
46 Correct 34 ms 105244 KB Output is correct
47 Correct 89 ms 103188 KB Output is correct
48 Correct 92 ms 103420 KB Output is correct
49 Correct 90 ms 103340 KB Output is correct
50 Correct 99 ms 103244 KB Output is correct
51 Correct 85 ms 103300 KB Output is correct
52 Correct 97 ms 103480 KB Output is correct
53 Correct 107 ms 103252 KB Output is correct
54 Correct 103 ms 103248 KB Output is correct
55 Correct 117 ms 107784 KB Output is correct
56 Correct 107 ms 107548 KB Output is correct
57 Correct 35 ms 107224 KB Output is correct
58 Correct 33 ms 107344 KB Output is correct
59 Correct 128 ms 107856 KB Output is correct
60 Correct 122 ms 107564 KB Output is correct
61 Correct 130 ms 107568 KB Output is correct
62 Correct 122 ms 107556 KB Output is correct
63 Correct 135 ms 107656 KB Output is correct
64 Correct 132 ms 107600 KB Output is correct
65 Correct 68 ms 107856 KB Output is correct
66 Correct 128 ms 108068 KB Output is correct
67 Correct 93 ms 105100 KB Output is correct
68 Correct 114 ms 107580 KB Output is correct
69 Correct 130 ms 107604 KB Output is correct
70 Correct 142 ms 107604 KB Output is correct
71 Correct 88 ms 107344 KB Output is correct
72 Correct 106 ms 107604 KB Output is correct
73 Correct 126 ms 108368 KB Output is correct
74 Correct 136 ms 108880 KB Output is correct
75 Correct 137 ms 109140 KB Output is correct
76 Correct 104 ms 106224 KB Output is correct
77 Correct 118 ms 108736 KB Output is correct
78 Correct 141 ms 108980 KB Output is correct
79 Correct 37 ms 108240 KB Output is correct
80 Correct 36 ms 108092 KB Output is correct
81 Correct 88 ms 109024 KB Output is correct
82 Correct 96 ms 106064 KB Output is correct
83 Correct 127 ms 109032 KB Output is correct
84 Correct 128 ms 108936 KB Output is correct
85 Correct 118 ms 108372 KB Output is correct
86 Correct 140 ms 108884 KB Output is correct
87 Correct 120 ms 108284 KB Output is correct
88 Correct 133 ms 108556 KB Output is correct
89 Correct 87 ms 105760 KB Output is correct
90 Correct 133 ms 108716 KB Output is correct
91 Correct 102 ms 108116 KB Output is correct
92 Correct 104 ms 107948 KB Output is correct
93 Correct 136 ms 108332 KB Output is correct
94 Correct 140 ms 108572 KB Output is correct
95 Correct 126 ms 108372 KB Output is correct
96 Correct 132 ms 108340 KB Output is correct
97 Correct 138 ms 108464 KB Output is correct
98 Correct 110 ms 108116 KB Output is correct
99 Correct 73 ms 108508 KB Output is correct
100 Correct 101 ms 108316 KB Output is correct
101 Correct 119 ms 108580 KB Output is correct
102 Correct 107 ms 108368 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 102228 KB Output is correct
2 Correct 20 ms 102236 KB Output is correct
3 Correct 21 ms 102232 KB Output is correct
4 Correct 20 ms 102236 KB Output is correct
5 Correct 19 ms 102232 KB Output is correct
6 Correct 18 ms 102236 KB Output is correct
7 Correct 21 ms 102232 KB Output is correct
8 Correct 21 ms 102232 KB Output is correct
9 Correct 21 ms 102236 KB Output is correct
10 Correct 21 ms 102348 KB Output is correct
11 Correct 20 ms 102232 KB Output is correct
12 Correct 23 ms 102736 KB Output is correct
13 Correct 19 ms 102368 KB Output is correct
14 Correct 19 ms 102136 KB Output is correct
15 Correct 20 ms 102236 KB Output is correct
16 Correct 20 ms 102236 KB Output is correct
17 Correct 21 ms 102388 KB Output is correct
18 Correct 20 ms 102236 KB Output is correct
19 Correct 20 ms 102344 KB Output is correct
20 Correct 20 ms 102232 KB Output is correct
21 Correct 20 ms 102236 KB Output is correct
22 Correct 23 ms 102236 KB Output is correct
23 Correct 21 ms 102588 KB Output is correct
24 Correct 21 ms 102340 KB Output is correct
25 Correct 18 ms 102232 KB Output is correct
26 Correct 19 ms 104284 KB Output is correct
27 Correct 21 ms 102272 KB Output is correct
28 Correct 20 ms 102232 KB Output is correct
29 Correct 21 ms 104284 KB Output is correct
30 Correct 21 ms 102236 KB Output is correct
31 Correct 21 ms 104284 KB Output is correct
32 Correct 20 ms 102236 KB Output is correct
33 Correct 21 ms 102172 KB Output is correct
34 Correct 20 ms 104284 KB Output is correct
35 Correct 21 ms 102236 KB Output is correct
36 Correct 21 ms 102360 KB Output is correct
37 Correct 19 ms 102236 KB Output is correct
38 Correct 20 ms 102236 KB Output is correct
39 Correct 101 ms 103760 KB Output is correct
40 Correct 94 ms 103256 KB Output is correct
41 Correct 96 ms 103424 KB Output is correct
42 Correct 95 ms 103508 KB Output is correct
43 Correct 97 ms 103252 KB Output is correct
44 Correct 105 ms 103380 KB Output is correct
45 Correct 32 ms 105180 KB Output is correct
46 Correct 34 ms 105244 KB Output is correct
47 Correct 89 ms 103188 KB Output is correct
48 Correct 92 ms 103420 KB Output is correct
49 Correct 90 ms 103340 KB Output is correct
50 Correct 99 ms 103244 KB Output is correct
51 Correct 85 ms 103300 KB Output is correct
52 Correct 97 ms 103480 KB Output is correct
53 Correct 107 ms 103252 KB Output is correct
54 Correct 103 ms 103248 KB Output is correct
55 Correct 556 ms 107484 KB Output is correct
56 Correct 417 ms 110676 KB Output is correct
57 Correct 601 ms 114000 KB Output is correct
58 Correct 467 ms 110420 KB Output is correct
59 Correct 426 ms 110520 KB Output is correct
60 Correct 633 ms 113604 KB Output is correct
61 Correct 83 ms 111620 KB Output is correct
62 Correct 89 ms 111140 KB Output is correct
63 Correct 654 ms 115100 KB Output is correct
64 Correct 658 ms 115212 KB Output is correct
65 Correct 537 ms 113304 KB Output is correct
66 Correct 555 ms 113744 KB Output is correct
67 Correct 535 ms 112980 KB Output is correct
68 Correct 571 ms 113488 KB Output is correct
69 Correct 588 ms 113532 KB Output is correct
70 Correct 600 ms 113408 KB Output is correct
71 Correct 609 ms 114260 KB Output is correct
72 Correct 592 ms 114584 KB Output is correct
73 Correct 621 ms 114404 KB Output is correct
74 Correct 590 ms 114408 KB Output is correct
75 Correct 639 ms 114288 KB Output is correct
76 Correct 634 ms 114276 KB Output is correct
77 Correct 658 ms 114252 KB Output is correct
78 Correct 623 ms 114272 KB Output is correct
79 Correct 462 ms 114260 KB Output is correct
80 Correct 518 ms 114552 KB Output is correct
81 Correct 444 ms 113500 KB Output is correct
82 Correct 117 ms 107784 KB Output is correct
83 Correct 107 ms 107548 KB Output is correct
84 Correct 35 ms 107224 KB Output is correct
85 Correct 33 ms 107344 KB Output is correct
86 Correct 128 ms 107856 KB Output is correct
87 Correct 122 ms 107564 KB Output is correct
88 Correct 130 ms 107568 KB Output is correct
89 Correct 122 ms 107556 KB Output is correct
90 Correct 135 ms 107656 KB Output is correct
91 Correct 132 ms 107600 KB Output is correct
92 Correct 68 ms 107856 KB Output is correct
93 Correct 128 ms 108068 KB Output is correct
94 Correct 93 ms 105100 KB Output is correct
95 Correct 114 ms 107580 KB Output is correct
96 Correct 130 ms 107604 KB Output is correct
97 Correct 142 ms 107604 KB Output is correct
98 Correct 88 ms 107344 KB Output is correct
99 Correct 106 ms 107604 KB Output is correct
100 Correct 126 ms 108368 KB Output is correct
101 Correct 136 ms 108880 KB Output is correct
102 Correct 137 ms 109140 KB Output is correct
103 Correct 104 ms 106224 KB Output is correct
104 Correct 118 ms 108736 KB Output is correct
105 Correct 141 ms 108980 KB Output is correct
106 Correct 37 ms 108240 KB Output is correct
107 Correct 36 ms 108092 KB Output is correct
108 Correct 88 ms 109024 KB Output is correct
109 Correct 96 ms 106064 KB Output is correct
110 Correct 127 ms 109032 KB Output is correct
111 Correct 128 ms 108936 KB Output is correct
112 Correct 118 ms 108372 KB Output is correct
113 Correct 140 ms 108884 KB Output is correct
114 Correct 120 ms 108284 KB Output is correct
115 Correct 133 ms 108556 KB Output is correct
116 Correct 87 ms 105760 KB Output is correct
117 Correct 133 ms 108716 KB Output is correct
118 Correct 102 ms 108116 KB Output is correct
119 Correct 104 ms 107948 KB Output is correct
120 Correct 136 ms 108332 KB Output is correct
121 Correct 140 ms 108572 KB Output is correct
122 Correct 126 ms 108372 KB Output is correct
123 Correct 132 ms 108340 KB Output is correct
124 Correct 138 ms 108464 KB Output is correct
125 Correct 110 ms 108116 KB Output is correct
126 Correct 73 ms 108508 KB Output is correct
127 Correct 101 ms 108316 KB Output is correct
128 Correct 119 ms 108580 KB Output is correct
129 Correct 107 ms 108368 KB Output is correct
130 Correct 615 ms 115540 KB Output is correct
131 Correct 449 ms 112888 KB Output is correct
132 Correct 609 ms 115492 KB Output is correct
133 Correct 595 ms 114872 KB Output is correct
134 Correct 536 ms 113744 KB Output is correct
135 Correct 643 ms 115184 KB Output is correct
136 Correct 669 ms 117272 KB Output is correct
137 Correct 679 ms 117016 KB Output is correct
138 Correct 519 ms 114916 KB Output is correct
139 Correct 564 ms 115236 KB Output is correct
140 Correct 582 ms 115024 KB Output is correct
141 Correct 576 ms 115028 KB Output is correct
142 Correct 592 ms 115028 KB Output is correct
143 Correct 609 ms 114780 KB Output is correct
144 Correct 599 ms 115096 KB Output is correct
145 Correct 577 ms 115012 KB Output is correct
146 Correct 582 ms 115028 KB Output is correct
147 Correct 600 ms 114948 KB Output is correct
148 Correct 600 ms 114972 KB Output is correct
149 Correct 591 ms 114840 KB Output is correct
150 Correct 290 ms 114708 KB Output is correct
151 Correct 500 ms 115364 KB Output is correct
152 Correct 491 ms 115256 KB Output is correct
153 Correct 449 ms 114328 KB Output is correct