oj.uz

답안 #685117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685117 2023-01-23T13:35:29 Z cig32 Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1137 ms 242444 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
struct query {
  int t, i, ans=0;
};
struct segtree_basic {
  struct node {
    int lazyval, mi, ma, sum; char lazytag;
    int len; // not changing
  };
  int stok;
  vector<node> st;
  void bu(int l, int r, int idx) {
    st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
    st[idx].lazytag = '?';
    st[idx].len = r - l + 1;
    if(l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    bu(l, mid, 2*idx+1);
    bu(mid+1, r, 2*idx+2);
  }
  void push_down(int idx) {
    if(st[idx].lazytag == '?') return;
    if(st[idx].lazytag == ':') {
      st[2*idx+1].lazyval = st[idx].lazyval;
      st[2*idx+1].mi = st[idx].lazyval;
      st[2*idx+1].ma = st[idx].lazyval;
      st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = ':';
 
      st[2*idx+2].lazyval = st[idx].lazyval;
      st[2*idx+2].mi = st[idx].lazyval;
      st[2*idx+2].ma = st[idx].lazyval;
      st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = ':';
 
    }
    else {
      st[2*idx+1].lazyval += st[idx].lazyval;
      st[2*idx+1].mi += st[idx].lazyval;
      st[2*idx+1].ma += st[idx].lazyval;
      st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
 
      st[2*idx+2].lazyval += st[idx].lazyval;
      st[2*idx+2].mi += st[idx].lazyval;
      st[2*idx+2].ma += st[idx].lazyval;
      st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
    }
    st[idx].lazytag = '?';
    st[idx].lazyval = 0;
  }
  void push_up(int idx) {
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
  }
  void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
    if(l <= constl && constr <= r) {
      st[idx].lazyval = val;
      st[idx].mi = val;
      st[idx].ma = val;
      st[idx].sum = val * st[idx].len;
      st[idx].lazytag = ':';
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
    else {
      u1(l, r, constl, mid, 2*idx+1, val);
      u1(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
    if(l <= constl && constr <= r) {
      st[idx].lazyval += val;
      st[idx].mi += val;
      st[idx].ma += val;
      st[idx].sum += val * st[idx].len;
      st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
    else {
      u2(l, r, constl, mid, 2*idx+1, val);
      u2(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  int qu1(int l, int r, int constl, int constr, int idx) { // range min
    if(l <= constl && constr <= r) return st[idx].mi;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1);
    else {
      return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
    }
  }
 
  int qu2(int l, int r, int constl, int constr, int idx) { // range max
    if(l <= constl && constr <= r) return st[idx].ma;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2); 
    else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1);
    else {
      return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
    }
  }
  int qu3(int l, int r, int constl, int constr, int idx) { // range sum
    if(l <= constl && constr <= r) return st[idx].sum;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1);
    else {
      return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2);
    }
  }
  int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu4(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu4(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu5(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu5(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu6(l, r, constl, mid, 2*idx+1, val);
    }
  }
  int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu7(l, r, constl, mid, 2*idx+1, val);
    }
  }
  public:
  void resize(int k) {
    st.resize(4*k + 10);
    stok = k;
    bu(0, k, 0);
  }
  void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
 
  void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
 
  int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
 
  int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); }
 
  int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
 
  int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
 
  int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
 
  int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); } 
 
  int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
int bit[MAXN];
void add(int x, int v) {
  for(;x<MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
  int s=0;
  for(;x;x-=x&-x) s += bit[x];
  return s;
}
void solve(int tc) {
  int n, q;
  cin >> n >> q;
  int p[n+1];
  for(int i=1; i<=n; i++) cin >> p[i];
  query r[q+1];
  vector<int> rr[n+1];
  for(int i=1; i<=q; i++) {
    cin >> r[i].t >> r[i].i;
    if(r[i].t == 0) r[i].ans = p[r[i].i];
    rr[min(r[i].t, n)].push_back(i);
  }
  segtree_basic stb;
  stb.resize(n);
  bool used[n+1];
  for(int i=1; i<=n; i++) used[i] = 0;
  int pos[n+1];
  for(int i=1; i<=n; i++) {
    pos[p[i]] = i;
    stb.range_add(i, i, p[i]);
  }
  deque<int> list[n+1];
  for(int i=n; i>=1; i--) {
    if(!used[i]) {
      int pa = pos[i];
      int s=0;
      for(int j=pa; j<=n; j++) {
        if(used[p[j]]) break;
        s++;
        list[i].push_back(p[j]);
        used[p[j]] = 1;
      }
      add(i, s);
    }
  }
  for(int i=1; i<=n; i++) {
    int lb = 1, rb = n;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      if(n/2 <= sum(mid)) rb = mid;
      else lb = mid + 1;
    }
    int pol = n/2 - sum(lb - 1); // position in the list, 1-based
    if(pol != list[lb].size()) { 
      if(pol <= list[lb].size() - pol) { // remove front
        deque<int> New;
        add(lb, -(int) (list[lb].size()));
        for(int j=0; j<pol; j++) {
          New.push_back(list[lb].front()); list[lb].pop_front();
        }
        list[lb].swap(New);
        add(lb, list[lb].size());
        // New is the unprocessed new array
        while(1) {
          int nf = New.front();
          int pnf = pos[nf];
          int res = stb.query_firstAtLeast(pnf, n, nf+1);
          if(res != -1)res = res - pnf;
          else res = 1e9;
          if(res < New.size()) { // take part
            if(res <= New.size() - res) { // take first res elements
              deque<int> bruhed;
              for(int j=0; j<res; j++) {
                bruhed.push_back(New.front());
                New.pop_front();
              }
              add(nf, res);
              list[nf].swap(bruhed);
            }
            else { // use O(back) naive complexity
              int ll = New.size() - res;
              vector<int> v;
              for(int j=0; j<ll; j++) {
                v.push_back(New.back());
                New.pop_back();
              }
              reverse(v.begin(), v.end());
              add(nf, New.size());
              list[nf].swap(New);
              for(int j=0; j<v.size(); j++) {
                int k = j;
                while(k+1 < v.size() && v[k+1] < v[j]) k++;
                deque<int> dq;
                for(int l=j; l<=k; l++) dq.push_back(v[l]);
                int dq0 = dq[0];
                add(dq0, dq.size());
                list[dq0].swap(dq);
                j = k;
              }
              break;
            }
          }
          else { // res >= New.size: take whole and end
            add(nf, New.size());
            list[nf].swap(New);
            break;
          }
        }
      }
      else { // remove back, complexity can be O(back) naive
        add(lb, - (int) list[lb].size());
        int ll = list[lb].size() - pol;
        vector<int> v;
        for(int j=0; j<ll; j++) {
          v.push_back(list[lb].back()); list[lb].pop_back();
        }
        reverse(v.begin(), v.end());
        add(lb, list[lb].size());
        for(int j=0; j<v.size(); j++) {
          int k = j;
          while(k+1 < v.size() && v[k+1] < v[j]) k++;
          deque<int> dq;
          for(int l=j; l<=k; l++) dq.push_back(v[l]);
          int dq0 = dq[0];
          add(dq0, dq.size());
          list[dq0].swap(dq);
          j = k;
        }
      }
    }
    for(int y: rr[i]) {
      int x = r[y].i;
      // find the x-th element
      int lb = 1, rb = n;
      while(lb < rb) {
        int mid = (lb + rb) >> 1;
        if(x <= sum(mid)) rb = mid;
        else lb = mid + 1;
      }
      int ord = x - sum(lb - 1);
      r[y].ans = list[lb][ord - 1];
    }
  }
  for(int i=1; i<=q; i++) cout << r[i].ans << " \n"[i == q];
}


int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

Main.cpp: In function 'void solve(long long int)':
Main.cpp:312:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  312 |     if(pol != list[lb].size()) {
      |        ~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:313:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  313 |       if(pol <= list[lb].size() - pol) { // remove front
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:328:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  328 |           if(res < New.size()) { // take part
      |              ~~~~^~~~~~~~~~~~
Main.cpp:329:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  329 |             if(res <= New.size() - res) { // take first res elements
      |                ~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:348:29: 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]
  348 |               for(int j=0; j<v.size(); j++) {
      |                            ~^~~~~~~~~
Main.cpp:350:27: 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]
  350 |                 while(k+1 < v.size() && v[k+1] < v[j]) k++;
      |                       ~~~~^~~~~~~~~~
Main.cpp:377:23: 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]
  377 |         for(int j=0; j<v.size(); j++) {
      |                      ~^~~~~~~~~
Main.cpp:379: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]
  379 |           while(k+1 < v.size() && v[k+1] < v[j]) k++;
      |                 ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 45940 KB Output is correct
2 Correct 390 ms 44496 KB Output is correct
3 Correct 360 ms 43004 KB Output is correct
4 Correct 286 ms 41680 KB Output is correct
5 Correct 325 ms 45768 KB Output is correct
6 Correct 292 ms 44636 KB Output is correct
7 Correct 349 ms 46632 KB Output is correct
8 Correct 303 ms 43556 KB Output is correct
9 Correct 302 ms 42084 KB Output is correct
10 Correct 310 ms 42504 KB Output is correct
11 Correct 335 ms 42752 KB Output is correct
12 Correct 230 ms 40320 KB Output is correct
13 Correct 296 ms 41912 KB Output is correct
14 Correct 324 ms 44560 KB Output is correct
15 Correct 319 ms 42884 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 191 ms 40916 KB Output is correct
18 Correct 203 ms 40540 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 658 ms 235852 KB Output is correct
2 Correct 651 ms 233624 KB Output is correct
3 Correct 534 ms 217796 KB Output is correct
4 Correct 602 ms 219864 KB Output is correct
5 Correct 620 ms 224628 KB Output is correct
6 Correct 566 ms 216240 KB Output is correct
7 Correct 604 ms 233888 KB Output is correct
8 Correct 630 ms 224040 KB Output is correct
9 Correct 580 ms 223548 KB Output is correct
10 Correct 581 ms 222300 KB Output is correct
11 Correct 480 ms 220844 KB Output is correct
12 Correct 528 ms 215272 KB Output is correct
13 Correct 571 ms 223536 KB Output is correct
14 Correct 475 ms 221944 KB Output is correct
15 Correct 659 ms 228744 KB Output is correct
16 Correct 193 ms 183712 KB Output is correct
17 Correct 377 ms 220652 KB Output is correct
18 Correct 498 ms 212576 KB Output is correct
19 Correct 252 ms 190880 KB Output is correct
20 Correct 302 ms 187288 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 98840 KB Output is correct
2 Correct 174 ms 97596 KB Output is correct
3 Correct 188 ms 95140 KB Output is correct
4 Correct 158 ms 95532 KB Output is correct
5 Correct 184 ms 98252 KB Output is correct
6 Correct 152 ms 94180 KB Output is correct
7 Correct 161 ms 97716 KB Output is correct
8 Correct 158 ms 93644 KB Output is correct
9 Correct 176 ms 97480 KB Output is correct
10 Correct 133 ms 92932 KB Output is correct
11 Correct 131 ms 96576 KB Output is correct
12 Correct 142 ms 93856 KB Output is correct
13 Correct 156 ms 93624 KB Output is correct
14 Correct 137 ms 96672 KB Output is correct
15 Correct 136 ms 95216 KB Output is correct
16 Correct 97 ms 92060 KB Output is correct
17 Correct 109 ms 92488 KB Output is correct
18 Correct 120 ms 92996 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 45940 KB Output is correct
2 Correct 390 ms 44496 KB Output is correct
3 Correct 360 ms 43004 KB Output is correct
4 Correct 286 ms 41680 KB Output is correct
5 Correct 325 ms 45768 KB Output is correct
6 Correct 292 ms 44636 KB Output is correct
7 Correct 349 ms 46632 KB Output is correct
8 Correct 303 ms 43556 KB Output is correct
9 Correct 302 ms 42084 KB Output is correct
10 Correct 310 ms 42504 KB Output is correct
11 Correct 335 ms 42752 KB Output is correct
12 Correct 230 ms 40320 KB Output is correct
13 Correct 296 ms 41912 KB Output is correct
14 Correct 324 ms 44560 KB Output is correct
15 Correct 319 ms 42884 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 191 ms 40916 KB Output is correct
18 Correct 203 ms 40540 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 658 ms 235852 KB Output is correct
22 Correct 651 ms 233624 KB Output is correct
23 Correct 534 ms 217796 KB Output is correct
24 Correct 602 ms 219864 KB Output is correct
25 Correct 620 ms 224628 KB Output is correct
26 Correct 566 ms 216240 KB Output is correct
27 Correct 604 ms 233888 KB Output is correct
28 Correct 630 ms 224040 KB Output is correct
29 Correct 580 ms 223548 KB Output is correct
30 Correct 581 ms 222300 KB Output is correct
31 Correct 480 ms 220844 KB Output is correct
32 Correct 528 ms 215272 KB Output is correct
33 Correct 571 ms 223536 KB Output is correct
34 Correct 475 ms 221944 KB Output is correct
35 Correct 659 ms 228744 KB Output is correct
36 Correct 193 ms 183712 KB Output is correct
37 Correct 377 ms 220652 KB Output is correct
38 Correct 498 ms 212576 KB Output is correct
39 Correct 252 ms 190880 KB Output is correct
40 Correct 302 ms 187288 KB Output is correct
41 Correct 197 ms 98840 KB Output is correct
42 Correct 174 ms 97596 KB Output is correct
43 Correct 188 ms 95140 KB Output is correct
44 Correct 158 ms 95532 KB Output is correct
45 Correct 184 ms 98252 KB Output is correct
46 Correct 152 ms 94180 KB Output is correct
47 Correct 161 ms 97716 KB Output is correct
48 Correct 158 ms 93644 KB Output is correct
49 Correct 176 ms 97480 KB Output is correct
50 Correct 133 ms 92932 KB Output is correct
51 Correct 131 ms 96576 KB Output is correct
52 Correct 142 ms 93856 KB Output is correct
53 Correct 156 ms 93624 KB Output is correct
54 Correct 137 ms 96672 KB Output is correct
55 Correct 136 ms 95216 KB Output is correct
56 Correct 97 ms 92060 KB Output is correct
57 Correct 109 ms 92488 KB Output is correct
58 Correct 120 ms 92996 KB Output is correct
59 Correct 1 ms 340 KB Output is correct
60 Correct 0 ms 340 KB Output is correct
61 Correct 1137 ms 242444 KB Output is correct
62 Correct 1088 ms 238180 KB Output is correct
63 Correct 1094 ms 231584 KB Output is correct
64 Correct 934 ms 232824 KB Output is correct
65 Correct 920 ms 239148 KB Output is correct
66 Correct 863 ms 229772 KB Output is correct
67 Correct 806 ms 236076 KB Output is correct
68 Correct 822 ms 226376 KB Output is correct
69 Correct 830 ms 235432 KB Output is correct
70 Correct 770 ms 224904 KB Output is correct
71 Correct 680 ms 232240 KB Output is correct
72 Correct 808 ms 226236 KB Output is correct
73 Correct 731 ms 226900 KB Output is correct
74 Correct 713 ms 234924 KB Output is correct
75 Correct 794 ms 231020 KB Output is correct
76 Correct 194 ms 183648 KB Output is correct
77 Correct 427 ms 221012 KB Output is correct
78 Correct 518 ms 221476 KB Output is correct
79 Correct 1 ms 340 KB Output is correct
80 Correct 1 ms 340 KB Output is correct