Submission #777583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
777583	2023-07-09T11:00:52 Z	Sam_a17	New Home (APIO18_new_home)	C++17	47 / 100	1946 ms	1048576 KB

new_home

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
// template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(Tree <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  // if(str == "input") {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  // } else if(str != "") {
    // freopen((str + ".in").c_str(), "r", stdin);
    // freopen((str + ".out").c_str(), "w", stdout);
  // }
}
 
const int N = 8e5, maxM = 3e5 + 10, inf = 1e8, infi = 2e9 + 10;
vector<pair<int, int>> to_add[N], to_erase[N];
int n, k, q;
 
struct node {
  int x, t, a, b;
};
 
vector<node> cand;

struct segTreeMax {  // Range Queries
  multiset<int> mt[N * 4];
  vector<int> mTree;
  int size;

  void init(ll n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    mTree.assign(2 * size - 1, 0);
  }

  void upd(int u, ll v, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      if(v >= 0) {
        mt[x].insert(v);
      } else {
        assert(mt[x].find(-v) != mt[x].end());
        mt[x].erase(mt[x].find(-v));
      }

      if(!mt[x].empty()) {
        mTree[x] = *prev(mt[x].end());
      } else {
        mTree[x] = -1;
      }
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, v, 2 * x + 1, lx, m);
    }else {
      upd(u, v, 2 * x + 2, m, rx);
    }
    mTree[x] = max(mTree[2 * x + 1], mTree[2 * x + 2]);
  }

  void upd(int u, ll v) {
    upd(u, v, 0, 0, size);
  }

  int qry(int l, int r, int x, int lx, int rx) { // range queries
    if(l >= rx || lx >= r) {
      return -1;
    }

    if(lx >= l && r >= rx) {
      return mTree[x];
    }

    int m = (rx + lx) / 2;
    int s1 = qry(l, r, 2 * x + 1, lx, m);
    int s2 = qry(l, r, 2 * x + 2, m, rx);
    return max(s1, s2);
  }

  int qry(int l, int r) {
    return qry(l, r, 0,0,size);
  }
};

struct segTreeMin {  // Range Queries
  multiset<int> mt[N * 4];
  vector<int> mTree;
  int size;

  void init(ll n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    mTree.assign(2 * size - 1, INT32_MAX);
  }

  void upd(int u, ll v, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      if(v >= 0) {
        mt[x].insert(v);
      } else {
        assert(mt[x].find(-v) != mt[x].end());
        mt[x].erase(mt[x].find(-v));
      }


      if(!mt[x].empty()) {
        mTree[x] = *mt[x].begin();
      } else {
        mTree[x] = INT32_MAX;
      }
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, v, 2 * x + 1, lx, m);
    }else {
      upd(u, v, 2 * x + 2, m, rx);
    }
    mTree[x] = min(mTree[2 * x + 1], mTree[2 * x + 2]);
  }

  void upd(int u, ll v) {
    upd(u, v, 0, 0, size);
  }

  int qry(int l, int r, int x, int lx, int rx) { // range queries
    if(l >= rx || lx >= r) {
      return INT32_MAX;
    }

    if(lx >= l && r >= rx) {
      return mTree[x];
    }

    int m = (rx + lx) / 2;
    int s1 = qry(l, r, 2 * x + 1, lx, m);
    int s2 = qry(l, r, 2 * x + 2, m, rx);
    return min(s1, s2);
  }

  int qry(int l, int r) {
    return qry(l, r, 0,0,size);
  }
};

segTreeMax rs;
segTreeMin ls;

vector<int> compress_times, compress_locations;
multiset<int> color[maxM];
map<int, int> mx_col[maxM];
vector<pair<int, int>> qr[N];
int pat[maxM];

unordered_map<int, int> mapi;

int get(int val) {
  return mapi[val];
}

void add_interval(int type, int l, int r) {
  int mid = (l + r + 1) / 2;
  l = get(l);
  r = get(r);
  int midone = get(mid - 1);
  mid = get(mid);
  
  if(mid <= r) {
    rs.upd(mid, r);
  }
  if(l < mid) {
    ls.upd(midone, l);
  }
}

void del_interval(int type, int l, int r) {
  int mid = (l + r + 1) / 2;
  
  l = get(l);
  r = get(r);
  int midone = get(mid - 1);
  mid = get(mid);

  if(mid <= r) rs.upd(mid, -r);
  if(l < mid) ls.upd(midone, -l);
}

void solve_() {
  cin >> n >> k >> q;
 
  for(int i = 1; i <= n; i++) {
    int x, t, a, b; 
    cin >> x >> t >> a >> b;
    
    compress_times.push_back(a);
    compress_times.push_back(b + 1);

    compress_locations.push_back(x);

    cand.push_back({x, t, a, b});
  }

  vector<pair<int, int>> queries;
  for(int i = 1; i <= q; i++) {
    int l, y; cin >> l >> y;
    compress_locations.push_back(l);
    compress_times.push_back(y);
    queries.emplace_back(l, y);
  }

  compress_locations.push_back(-infi);
  compress_locations.push_back(infi);
  
  sort(all(compress_times));
  uniq(compress_times);


  for(auto &i: cand) {
    i.a = lower_bound(all(compress_times), i.a) - compress_times.begin();
    i.b = lower_bound(all(compress_times), i.b + 1) - compress_times.begin();

    to_add[i.a].push_back({i.x, i.t});
    to_erase[i.b].push_back({i.x, i.t});
  } 

  for(int i = 1; i <= k; i++) {
    color[i].insert(-infi);
    color[i].insert(infi);
  }

  for(int i = 0; i < sz(compress_times); i++) {
    for(auto j: to_add[i]) {
      if(color[j.second].find(j.first) != color[j.second].end()) {
        mx_col[j.second][j.first]++;
        continue;
      }

      color[j.second].insert(j.first);

      mx_col[j.second][j.first] = 1;
      auto it = color[j.second].find(j.first);
      auto it_prev = prev(it), it_next = next(it);

      int mid1 = (*it_next + j.first + 1) / 2;
      int mid2 = (*it_prev + j.first + 1) / 2;
      
      compress_locations.push_back(mid1);
      compress_locations.push_back(mid1 - 1);
      
      compress_locations.push_back(mid2);
      compress_locations.push_back(mid2 - 1);
    }


    // tex, tip
    for(auto j: to_erase[i]) {
      // color[j.second]

      mx_col[j.second][j.first]--;
      if(mx_col[j.second][j.first] == 0) {

        auto it = color[j.second].find(j.first);
        auto it_prev = prev(it), it_next = next(it);

        int mid1 = (*it_next + *it_prev + 1) / 2;
        
        compress_locations.push_back(mid1);
        compress_locations.push_back(mid1 - 1);
 
        color[j.second].erase(j.first);
      }
    }
  }

  int it = 1;
  for(auto &i: queries) {
    i.second = lower_bound(all(compress_times), i.second) - compress_times.begin();
    qr[i.second].emplace_back(i.first, it);
    it++;
  }

  sort(all(compress_locations));
  uniq(compress_locations);
  ls.init(sz(compress_locations) + 2);
  rs.init(sz(compress_locations) + 2);

  for(int i = 1; i <= k; i++) {
    color[i].clear();
    mx_col[i].clear();
    
    color[i].insert(-infi);
    color[i].insert(infi);
  }

  vector<bool> empty(k + 1, true);
  int emp = k;

  mapi.reserve(2 * sz(compress_locations) + 2);
  for(int i = 0; i < sz(compress_locations); i++) {
    mapi[compress_locations[i]] = i;
  }

  for(int i = 0; i < sz(compress_times); i++) {
    for(auto j: to_add[i]) {
      if(color[j.second].find(j.first) != color[j.second].end()) {
        mx_col[j.second][j.first]++;
        continue;
      }

      mx_col[j.second][j.first] = 1;
      color[j.second].insert(j.first);
      if(sz(color[j.second]) == 3) {
        assert(empty[j.second]);
        empty[j.second] = false;
        emp--;
      }

      // ete inchvor bani aranqna
      auto it = color[j.second].find(j.first);
      assert(it != color[j.second].begin());
      assert(it != prev(color[j.second].end()));
      auto it_prev = prev(it), it_next = next(it);

      int mid1 = (*it_next + j.first + 1) / 2;
      int mid2 = (*it_prev + j.first + 1) / 2;


      add_interval(j.second, *it_prev, j.first);
      add_interval(j.second, j.first, *it_next);


      if(*it_prev != -infi || *it_next != infi) {
        del_interval(j.second, *it_prev, *it_next);
      }
    }

    // tex, tip
    for(auto j: to_erase[i]) {

      mx_col[j.second][j.first]--;
      if(mx_col[j.second][j.first] == 0) {

        auto it = color[j.second].find(j.first);

        if(sz(color[j.second]) == 3) {
          empty[j.second] = true;
          emp++;
        }

        auto it_prev = prev(it), it_next = next(it);
        del_interval(j.second, *it_prev, j.first);
        del_interval(j.second, j.first, *it_next);

        if(*it_prev != -infi || *it_next != infi) {
          add_interval(j.second, *it_prev, *it_next);
        }

        color[j.second].erase(j.first);
      }
    }

    for(auto j: qr[i]) {
      if(emp) {
        pat[j.second] = -1;
      } else {
        int cur = lower_bound(all(compress_locations), j.first) - compress_locations.begin();
        int li = ls.qry(cur, sz(compress_locations) + 1);
        int ri = rs.qry(0, cur + 1);

        if(li <= cur) {
          pat[j.second] = max(pat[j.second], j.first - compress_locations[li]);
        }

        if(ri >= cur) {
          pat[j.second] = max(pat[j.second], compress_locations[ri] - j.first);
        }
      }
    }
  }

  for(int i = 1; i <= q; i++) {
    cout << pat[i] << '\n';
  }
 }
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

new_home.cpp: In function 'void solve_()':
new_home.cpp:399:11: warning: unused variable 'mid1' [-Wunused-variable]
  399 |       int mid1 = (*it_next + j.first + 1) / 2;
      |           ^~~~
new_home.cpp:400:11: warning: unused variable 'mid2' [-Wunused-variable]
  400 |       int mid2 = (*it_prev + j.first + 1) / 2;
      |           ^~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	385432 KB	Output is correct
2	Correct	149 ms	385372 KB	Output is correct
3	Correct	170 ms	385540 KB	Output is correct
4	Correct	148 ms	385388 KB	Output is correct
5	Correct	149 ms	385504 KB	Output is correct
6	Correct	150 ms	385764 KB	Output is correct
7	Correct	152 ms	385856 KB	Output is correct
8	Correct	155 ms	385788 KB	Output is correct
9	Correct	150 ms	385780 KB	Output is correct
10	Correct	152 ms	385768 KB	Output is correct
11	Correct	155 ms	385780 KB	Output is correct
12	Correct	153 ms	385784 KB	Output is correct
13	Correct	150 ms	385676 KB	Output is correct
14	Correct	156 ms	385740 KB	Output is correct
15	Correct	165 ms	385744 KB	Output is correct
16	Correct	165 ms	385724 KB	Output is correct
17	Correct	152 ms	385812 KB	Output is correct
18	Correct	154 ms	385716 KB	Output is correct
19	Correct	152 ms	385792 KB	Output is correct
20	Correct	153 ms	385828 KB	Output is correct
21	Correct	149 ms	385660 KB	Output is correct
22	Correct	178 ms	385796 KB	Output is correct
23	Correct	155 ms	385856 KB	Output is correct
24	Correct	153 ms	385736 KB	Output is correct
25	Correct	151 ms	385716 KB	Output is correct
26	Correct	159 ms	385776 KB	Output is correct
27	Correct	151 ms	385540 KB	Output is correct
28	Correct	154 ms	385712 KB	Output is correct
29	Correct	155 ms	385696 KB	Output is correct
30	Correct	150 ms	385748 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	385432 KB	Output is correct
2	Correct	149 ms	385372 KB	Output is correct
3	Correct	170 ms	385540 KB	Output is correct
4	Correct	148 ms	385388 KB	Output is correct
5	Correct	149 ms	385504 KB	Output is correct
6	Correct	150 ms	385764 KB	Output is correct
7	Correct	152 ms	385856 KB	Output is correct
8	Correct	155 ms	385788 KB	Output is correct
9	Correct	150 ms	385780 KB	Output is correct
10	Correct	152 ms	385768 KB	Output is correct
11	Correct	155 ms	385780 KB	Output is correct
12	Correct	153 ms	385784 KB	Output is correct
13	Correct	150 ms	385676 KB	Output is correct
14	Correct	156 ms	385740 KB	Output is correct
15	Correct	165 ms	385744 KB	Output is correct
16	Correct	165 ms	385724 KB	Output is correct
17	Correct	152 ms	385812 KB	Output is correct
18	Correct	154 ms	385716 KB	Output is correct
19	Correct	152 ms	385792 KB	Output is correct
20	Correct	153 ms	385828 KB	Output is correct
21	Correct	149 ms	385660 KB	Output is correct
22	Correct	178 ms	385796 KB	Output is correct
23	Correct	155 ms	385856 KB	Output is correct
24	Correct	153 ms	385736 KB	Output is correct
25	Correct	151 ms	385716 KB	Output is correct
26	Correct	159 ms	385776 KB	Output is correct
27	Correct	151 ms	385540 KB	Output is correct
28	Correct	154 ms	385712 KB	Output is correct
29	Correct	155 ms	385696 KB	Output is correct
30	Correct	150 ms	385748 KB	Output is correct
31	Correct	1045 ms	442256 KB	Output is correct
32	Correct	196 ms	391044 KB	Output is correct
33	Correct	989 ms	433792 KB	Output is correct
34	Correct	952 ms	433628 KB	Output is correct
35	Correct	1010 ms	442016 KB	Output is correct
36	Correct	1050 ms	441900 KB	Output is correct
37	Correct	760 ms	432052 KB	Output is correct
38	Correct	731 ms	431808 KB	Output is correct
39	Correct	631 ms	431740 KB	Output is correct
40	Correct	650 ms	431560 KB	Output is correct
41	Correct	824 ms	437116 KB	Output is correct
42	Correct	876 ms	437020 KB	Output is correct
43	Correct	194 ms	393244 KB	Output is correct
44	Correct	874 ms	437152 KB	Output is correct
45	Correct	821 ms	437144 KB	Output is correct
46	Correct	812 ms	437044 KB	Output is correct
47	Correct	551 ms	434552 KB	Output is correct
48	Correct	531 ms	434424 KB	Output is correct
49	Correct	581 ms	435996 KB	Output is correct
50	Correct	692 ms	436548 KB	Output is correct
51	Correct	773 ms	435908 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1668 ms	1048576 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1946 ms	1048576 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	385432 KB	Output is correct
2	Correct	149 ms	385372 KB	Output is correct
3	Correct	170 ms	385540 KB	Output is correct
4	Correct	148 ms	385388 KB	Output is correct
5	Correct	149 ms	385504 KB	Output is correct
6	Correct	150 ms	385764 KB	Output is correct
7	Correct	152 ms	385856 KB	Output is correct
8	Correct	155 ms	385788 KB	Output is correct
9	Correct	150 ms	385780 KB	Output is correct
10	Correct	152 ms	385768 KB	Output is correct
11	Correct	155 ms	385780 KB	Output is correct
12	Correct	153 ms	385784 KB	Output is correct
13	Correct	150 ms	385676 KB	Output is correct
14	Correct	156 ms	385740 KB	Output is correct
15	Correct	165 ms	385744 KB	Output is correct
16	Correct	165 ms	385724 KB	Output is correct
17	Correct	152 ms	385812 KB	Output is correct
18	Correct	154 ms	385716 KB	Output is correct
19	Correct	152 ms	385792 KB	Output is correct
20	Correct	153 ms	385828 KB	Output is correct
21	Correct	149 ms	385660 KB	Output is correct
22	Correct	178 ms	385796 KB	Output is correct
23	Correct	155 ms	385856 KB	Output is correct
24	Correct	153 ms	385736 KB	Output is correct
25	Correct	151 ms	385716 KB	Output is correct
26	Correct	159 ms	385776 KB	Output is correct
27	Correct	151 ms	385540 KB	Output is correct
28	Correct	154 ms	385712 KB	Output is correct
29	Correct	155 ms	385696 KB	Output is correct
30	Correct	150 ms	385748 KB	Output is correct
31	Correct	1045 ms	442256 KB	Output is correct
32	Correct	196 ms	391044 KB	Output is correct
33	Correct	989 ms	433792 KB	Output is correct
34	Correct	952 ms	433628 KB	Output is correct
35	Correct	1010 ms	442016 KB	Output is correct
36	Correct	1050 ms	441900 KB	Output is correct
37	Correct	760 ms	432052 KB	Output is correct
38	Correct	731 ms	431808 KB	Output is correct
39	Correct	631 ms	431740 KB	Output is correct
40	Correct	650 ms	431560 KB	Output is correct
41	Correct	824 ms	437116 KB	Output is correct
42	Correct	876 ms	437020 KB	Output is correct
43	Correct	194 ms	393244 KB	Output is correct
44	Correct	874 ms	437152 KB	Output is correct
45	Correct	821 ms	437144 KB	Output is correct
46	Correct	812 ms	437044 KB	Output is correct
47	Correct	551 ms	434552 KB	Output is correct
48	Correct	531 ms	434424 KB	Output is correct
49	Correct	581 ms	435996 KB	Output is correct
50	Correct	692 ms	436548 KB	Output is correct
51	Correct	773 ms	435908 KB	Output is correct
52	Correct	781 ms	445344 KB	Output is correct
53	Correct	761 ms	436412 KB	Output is correct
54	Correct	886 ms	441192 KB	Output is correct
55	Correct	757 ms	438084 KB	Output is correct
56	Correct	746 ms	440204 KB	Output is correct
57	Correct	800 ms	435484 KB	Output is correct
58	Correct	754 ms	436792 KB	Output is correct
59	Correct	825 ms	439164 KB	Output is correct
60	Correct	774 ms	434404 KB	Output is correct
61	Correct	309 ms	414196 KB	Output is correct
62	Correct	735 ms	445608 KB	Output is correct
63	Correct	908 ms	442212 KB	Output is correct
64	Correct	952 ms	439764 KB	Output is correct
65	Correct	995 ms	436064 KB	Output is correct
66	Correct	923 ms	434308 KB	Output is correct
67	Correct	464 ms	400228 KB	Output is correct

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	385432 KB	Output is correct
2	Correct	149 ms	385372 KB	Output is correct
3	Correct	170 ms	385540 KB	Output is correct
4	Correct	148 ms	385388 KB	Output is correct
5	Correct	149 ms	385504 KB	Output is correct
6	Correct	150 ms	385764 KB	Output is correct
7	Correct	152 ms	385856 KB	Output is correct
8	Correct	155 ms	385788 KB	Output is correct
9	Correct	150 ms	385780 KB	Output is correct
10	Correct	152 ms	385768 KB	Output is correct
11	Correct	155 ms	385780 KB	Output is correct
12	Correct	153 ms	385784 KB	Output is correct
13	Correct	150 ms	385676 KB	Output is correct
14	Correct	156 ms	385740 KB	Output is correct
15	Correct	165 ms	385744 KB	Output is correct
16	Correct	165 ms	385724 KB	Output is correct
17	Correct	152 ms	385812 KB	Output is correct
18	Correct	154 ms	385716 KB	Output is correct
19	Correct	152 ms	385792 KB	Output is correct
20	Correct	153 ms	385828 KB	Output is correct
21	Correct	149 ms	385660 KB	Output is correct
22	Correct	178 ms	385796 KB	Output is correct
23	Correct	155 ms	385856 KB	Output is correct
24	Correct	153 ms	385736 KB	Output is correct
25	Correct	151 ms	385716 KB	Output is correct
26	Correct	159 ms	385776 KB	Output is correct
27	Correct	151 ms	385540 KB	Output is correct
28	Correct	154 ms	385712 KB	Output is correct
29	Correct	155 ms	385696 KB	Output is correct
30	Correct	150 ms	385748 KB	Output is correct
31	Correct	1045 ms	442256 KB	Output is correct
32	Correct	196 ms	391044 KB	Output is correct
33	Correct	989 ms	433792 KB	Output is correct
34	Correct	952 ms	433628 KB	Output is correct
35	Correct	1010 ms	442016 KB	Output is correct
36	Correct	1050 ms	441900 KB	Output is correct
37	Correct	760 ms	432052 KB	Output is correct
38	Correct	731 ms	431808 KB	Output is correct
39	Correct	631 ms	431740 KB	Output is correct
40	Correct	650 ms	431560 KB	Output is correct
41	Correct	824 ms	437116 KB	Output is correct
42	Correct	876 ms	437020 KB	Output is correct
43	Correct	194 ms	393244 KB	Output is correct
44	Correct	874 ms	437152 KB	Output is correct
45	Correct	821 ms	437144 KB	Output is correct
46	Correct	812 ms	437044 KB	Output is correct
47	Correct	551 ms	434552 KB	Output is correct
48	Correct	531 ms	434424 KB	Output is correct
49	Correct	581 ms	435996 KB	Output is correct
50	Correct	692 ms	436548 KB	Output is correct
51	Correct	773 ms	435908 KB	Output is correct
52	Runtime error	1668 ms	1048576 KB	Execution killed with signal 11
53	Halted	0 ms	0 KB	-