Submission #777662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
777662	2023-07-09T12:31:18 Z	Sam_a17	New Home (APIO18_new_home)	C++17	57 / 100	5000 ms	472360 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 = 2e6 + 10 + 4e5 + 10, maxM = 3e5 + 10, inf = 1e8, infi = 2e9 + 10;
vector<pair<pair<int, int>, int>> to_add[N];
int n, k, q;
 
struct node {
  int x, t, a, b;
};
 
vector<node> cand;

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

  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) {
      x -= sub;
      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 + sub] = *prev(mt[x].end());
      } else {
        mTree[x + sub] = -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 gt(int u, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      sub = x;
      return x;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      return gt(u, 2 * x + 1, lx, m);
    }else {
      return gt(u, 2 * x + 2, m, rx);
    }
  }

  int gt(int u) {
    return gt(u, 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];
  vector<int> mTree;
  int size;
  int sub;

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

  int ind(int xx) {
    if(xx >= sub) {
      return xx - sub;
    } else {
      return xx;
    }
  }

  void upd(int u, ll v, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      x -= sub;
      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 + sub] = *mt[x].begin();
      } else {
        mTree[x + sub] = 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 gt(int u, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      sub = x;
      return x;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      return gt(u, 2 * x + 1, lx, m);
    }else {
      return gt(u, 2 * x + 2, m, rx);
    }
  }

  int gt(int u) {
    return gt(u, 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;
map<int, int> mx_col[maxM];
int pat[maxM];

int get(int val) {
  return lower_bound(all(compress_locations), val) - compress_locations.begin();
}

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 = midone + 1;
  
  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 = midone + 1;

  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}, 1});
    to_add[i.b].push_back({{i.x, i.t}, 2});
  } 

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

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

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

        int mid1 = (it_next->first + j.first + 1) / 2;
        int mid2 = (it_prev->first + 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);
      } else if(cc.second == 2) {
        auto j = cc.first;
        mx_col[j.second][j.first]--;
        if(mx_col[j.second][j.first] == 0) {

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

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

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

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

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

  vector<bool> empty(k + 1, true);
  int emp = k;
  for(int i = 0; i < sz(compress_times); i++) {
    for(auto cc: to_add[i]) {
      if(cc.second == 1) { 
        auto j = cc.first;
        if(mx_col[j.second].find(j.first) != mx_col[j.second].end()) {
          mx_col[j.second][j.first]++;
          continue;
        }

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

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

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

        add_interval(j.second, it_prev->first, j.first);
        add_interval(j.second, j.first, it_next->first);

        if(it_prev->first != -infi || it_next->first != infi) {
          del_interval(j.second, it_prev->first, it_next->first);
        }
      } else if(cc.second == 2) {
        auto j = cc.first;
        mx_col[j.second][j.first]--;
        if(mx_col[j.second][j.first] == 0) {

          auto it = mx_col[j.second].find(j.first);
          if(sz(mx_col[j.second]) == 3) {
            empty[j.second] = true;
            emp++;
          }

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

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

          mx_col[j.second].erase(j.first);
        }
      } else {
        auto j = cc.first;
        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:429:13: warning: unused variable 'mid1' [-Wunused-variable]
  429 |         int mid1 = (it_next->first + j.first + 1) / 2;
      |             ^~~~
new_home.cpp:430:13: warning: unused variable 'mid2' [-Wunused-variable]
  430 |         int mid2 = (it_prev->first + j.first + 1) / 2;
      |             ^~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	296216 KB	Output is correct
2	Correct	136 ms	296160 KB	Output is correct
3	Correct	122 ms	296200 KB	Output is correct
4	Correct	126 ms	296220 KB	Output is correct
5	Correct	122 ms	296260 KB	Output is correct
6	Correct	123 ms	296268 KB	Output is correct
7	Correct	123 ms	296392 KB	Output is correct
8	Correct	130 ms	296512 KB	Output is correct
9	Correct	125 ms	296504 KB	Output is correct
10	Correct	126 ms	296324 KB	Output is correct
11	Correct	140 ms	296380 KB	Output is correct
12	Correct	123 ms	296348 KB	Output is correct
13	Correct	122 ms	296392 KB	Output is correct
14	Correct	127 ms	296440 KB	Output is correct
15	Correct	129 ms	296436 KB	Output is correct
16	Correct	123 ms	296392 KB	Output is correct
17	Correct	132 ms	296420 KB	Output is correct
18	Correct	133 ms	296436 KB	Output is correct
19	Correct	135 ms	296432 KB	Output is correct
20	Correct	141 ms	296340 KB	Output is correct
21	Correct	129 ms	296416 KB	Output is correct
22	Correct	133 ms	296496 KB	Output is correct
23	Correct	127 ms	296468 KB	Output is correct
24	Correct	123 ms	296372 KB	Output is correct
25	Correct	121 ms	296420 KB	Output is correct
26	Correct	129 ms	296404 KB	Output is correct
27	Correct	122 ms	296232 KB	Output is correct
28	Correct	122 ms	296404 KB	Output is correct
29	Correct	125 ms	296284 KB	Output is correct
30	Correct	201 ms	296388 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	296216 KB	Output is correct
2	Correct	136 ms	296160 KB	Output is correct
3	Correct	122 ms	296200 KB	Output is correct
4	Correct	126 ms	296220 KB	Output is correct
5	Correct	122 ms	296260 KB	Output is correct
6	Correct	123 ms	296268 KB	Output is correct
7	Correct	123 ms	296392 KB	Output is correct
8	Correct	130 ms	296512 KB	Output is correct
9	Correct	125 ms	296504 KB	Output is correct
10	Correct	126 ms	296324 KB	Output is correct
11	Correct	140 ms	296380 KB	Output is correct
12	Correct	123 ms	296348 KB	Output is correct
13	Correct	122 ms	296392 KB	Output is correct
14	Correct	127 ms	296440 KB	Output is correct
15	Correct	129 ms	296436 KB	Output is correct
16	Correct	123 ms	296392 KB	Output is correct
17	Correct	132 ms	296420 KB	Output is correct
18	Correct	133 ms	296436 KB	Output is correct
19	Correct	135 ms	296432 KB	Output is correct
20	Correct	141 ms	296340 KB	Output is correct
21	Correct	129 ms	296416 KB	Output is correct
22	Correct	133 ms	296496 KB	Output is correct
23	Correct	127 ms	296468 KB	Output is correct
24	Correct	123 ms	296372 KB	Output is correct
25	Correct	121 ms	296420 KB	Output is correct
26	Correct	129 ms	296404 KB	Output is correct
27	Correct	122 ms	296232 KB	Output is correct
28	Correct	122 ms	296404 KB	Output is correct
29	Correct	125 ms	296284 KB	Output is correct
30	Correct	201 ms	296388 KB	Output is correct
31	Correct	859 ms	324152 KB	Output is correct
32	Correct	170 ms	302332 KB	Output is correct
33	Correct	801 ms	318560 KB	Output is correct
34	Correct	864 ms	319284 KB	Output is correct
35	Correct	897 ms	324888 KB	Output is correct
36	Correct	824 ms	324704 KB	Output is correct
37	Correct	627 ms	317036 KB	Output is correct
38	Correct	623 ms	316848 KB	Output is correct
39	Correct	539 ms	316660 KB	Output is correct
40	Correct	597 ms	316764 KB	Output is correct
41	Correct	686 ms	321596 KB	Output is correct
42	Correct	654 ms	321364 KB	Output is correct
43	Correct	191 ms	304228 KB	Output is correct
44	Correct	687 ms	321576 KB	Output is correct
45	Correct	674 ms	321184 KB	Output is correct
46	Correct	626 ms	321132 KB	Output is correct
47	Correct	446 ms	320624 KB	Output is correct
48	Correct	449 ms	320408 KB	Output is correct
49	Correct	495 ms	320624 KB	Output is correct
50	Correct	519 ms	321096 KB	Output is correct
51	Correct	504 ms	320576 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4485 ms	465564 KB	Output is correct
2	Correct	4764 ms	444656 KB	Output is correct
3	Correct	3062 ms	469456 KB	Output is correct
4	Correct	4174 ms	471620 KB	Output is correct
5	Correct	4388 ms	444492 KB	Output is correct
6	Correct	4615 ms	444732 KB	Output is correct
7	Correct	2760 ms	469568 KB	Output is correct
8	Correct	3303 ms	472360 KB	Output is correct
9	Correct	3503 ms	456996 KB	Output is correct
10	Correct	3725 ms	445804 KB	Output is correct
11	Correct	2447 ms	443752 KB	Output is correct
12	Correct	2487 ms	445032 KB	Output is correct

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5062 ms	453388 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	296216 KB	Output is correct
2	Correct	136 ms	296160 KB	Output is correct
3	Correct	122 ms	296200 KB	Output is correct
4	Correct	126 ms	296220 KB	Output is correct
5	Correct	122 ms	296260 KB	Output is correct
6	Correct	123 ms	296268 KB	Output is correct
7	Correct	123 ms	296392 KB	Output is correct
8	Correct	130 ms	296512 KB	Output is correct
9	Correct	125 ms	296504 KB	Output is correct
10	Correct	126 ms	296324 KB	Output is correct
11	Correct	140 ms	296380 KB	Output is correct
12	Correct	123 ms	296348 KB	Output is correct
13	Correct	122 ms	296392 KB	Output is correct
14	Correct	127 ms	296440 KB	Output is correct
15	Correct	129 ms	296436 KB	Output is correct
16	Correct	123 ms	296392 KB	Output is correct
17	Correct	132 ms	296420 KB	Output is correct
18	Correct	133 ms	296436 KB	Output is correct
19	Correct	135 ms	296432 KB	Output is correct
20	Correct	141 ms	296340 KB	Output is correct
21	Correct	129 ms	296416 KB	Output is correct
22	Correct	133 ms	296496 KB	Output is correct
23	Correct	127 ms	296468 KB	Output is correct
24	Correct	123 ms	296372 KB	Output is correct
25	Correct	121 ms	296420 KB	Output is correct
26	Correct	129 ms	296404 KB	Output is correct
27	Correct	122 ms	296232 KB	Output is correct
28	Correct	122 ms	296404 KB	Output is correct
29	Correct	125 ms	296284 KB	Output is correct
30	Correct	201 ms	296388 KB	Output is correct
31	Correct	859 ms	324152 KB	Output is correct
32	Correct	170 ms	302332 KB	Output is correct
33	Correct	801 ms	318560 KB	Output is correct
34	Correct	864 ms	319284 KB	Output is correct
35	Correct	897 ms	324888 KB	Output is correct
36	Correct	824 ms	324704 KB	Output is correct
37	Correct	627 ms	317036 KB	Output is correct
38	Correct	623 ms	316848 KB	Output is correct
39	Correct	539 ms	316660 KB	Output is correct
40	Correct	597 ms	316764 KB	Output is correct
41	Correct	686 ms	321596 KB	Output is correct
42	Correct	654 ms	321364 KB	Output is correct
43	Correct	191 ms	304228 KB	Output is correct
44	Correct	687 ms	321576 KB	Output is correct
45	Correct	674 ms	321184 KB	Output is correct
46	Correct	626 ms	321132 KB	Output is correct
47	Correct	446 ms	320624 KB	Output is correct
48	Correct	449 ms	320408 KB	Output is correct
49	Correct	495 ms	320624 KB	Output is correct
50	Correct	519 ms	321096 KB	Output is correct
51	Correct	504 ms	320576 KB	Output is correct
52	Correct	635 ms	334936 KB	Output is correct
53	Correct	618 ms	328068 KB	Output is correct
54	Correct	825 ms	328776 KB	Output is correct
55	Correct	676 ms	325396 KB	Output is correct
56	Correct	658 ms	327772 KB	Output is correct
57	Correct	729 ms	321852 KB	Output is correct
58	Correct	687 ms	324676 KB	Output is correct
59	Correct	674 ms	327188 KB	Output is correct
60	Correct	679 ms	320964 KB	Output is correct
61	Correct	299 ms	323620 KB	Output is correct
62	Correct	667 ms	335052 KB	Output is correct
63	Correct	772 ms	329404 KB	Output is correct
64	Correct	818 ms	326776 KB	Output is correct
65	Correct	861 ms	322360 KB	Output is correct
66	Correct	722 ms	320364 KB	Output is correct
67	Correct	395 ms	309996 KB	Output is correct

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	296216 KB	Output is correct
2	Correct	136 ms	296160 KB	Output is correct
3	Correct	122 ms	296200 KB	Output is correct
4	Correct	126 ms	296220 KB	Output is correct
5	Correct	122 ms	296260 KB	Output is correct
6	Correct	123 ms	296268 KB	Output is correct
7	Correct	123 ms	296392 KB	Output is correct
8	Correct	130 ms	296512 KB	Output is correct
9	Correct	125 ms	296504 KB	Output is correct
10	Correct	126 ms	296324 KB	Output is correct
11	Correct	140 ms	296380 KB	Output is correct
12	Correct	123 ms	296348 KB	Output is correct
13	Correct	122 ms	296392 KB	Output is correct
14	Correct	127 ms	296440 KB	Output is correct
15	Correct	129 ms	296436 KB	Output is correct
16	Correct	123 ms	296392 KB	Output is correct
17	Correct	132 ms	296420 KB	Output is correct
18	Correct	133 ms	296436 KB	Output is correct
19	Correct	135 ms	296432 KB	Output is correct
20	Correct	141 ms	296340 KB	Output is correct
21	Correct	129 ms	296416 KB	Output is correct
22	Correct	133 ms	296496 KB	Output is correct
23	Correct	127 ms	296468 KB	Output is correct
24	Correct	123 ms	296372 KB	Output is correct
25	Correct	121 ms	296420 KB	Output is correct
26	Correct	129 ms	296404 KB	Output is correct
27	Correct	122 ms	296232 KB	Output is correct
28	Correct	122 ms	296404 KB	Output is correct
29	Correct	125 ms	296284 KB	Output is correct
30	Correct	201 ms	296388 KB	Output is correct
31	Correct	859 ms	324152 KB	Output is correct
32	Correct	170 ms	302332 KB	Output is correct
33	Correct	801 ms	318560 KB	Output is correct
34	Correct	864 ms	319284 KB	Output is correct
35	Correct	897 ms	324888 KB	Output is correct
36	Correct	824 ms	324704 KB	Output is correct
37	Correct	627 ms	317036 KB	Output is correct
38	Correct	623 ms	316848 KB	Output is correct
39	Correct	539 ms	316660 KB	Output is correct
40	Correct	597 ms	316764 KB	Output is correct
41	Correct	686 ms	321596 KB	Output is correct
42	Correct	654 ms	321364 KB	Output is correct
43	Correct	191 ms	304228 KB	Output is correct
44	Correct	687 ms	321576 KB	Output is correct
45	Correct	674 ms	321184 KB	Output is correct
46	Correct	626 ms	321132 KB	Output is correct
47	Correct	446 ms	320624 KB	Output is correct
48	Correct	449 ms	320408 KB	Output is correct
49	Correct	495 ms	320624 KB	Output is correct
50	Correct	519 ms	321096 KB	Output is correct
51	Correct	504 ms	320576 KB	Output is correct
52	Correct	4485 ms	465564 KB	Output is correct
53	Correct	4764 ms	444656 KB	Output is correct
54	Correct	3062 ms	469456 KB	Output is correct
55	Correct	4174 ms	471620 KB	Output is correct
56	Correct	4388 ms	444492 KB	Output is correct
57	Correct	4615 ms	444732 KB	Output is correct
58	Correct	2760 ms	469568 KB	Output is correct
59	Correct	3303 ms	472360 KB	Output is correct
60	Correct	3503 ms	456996 KB	Output is correct
61	Correct	3725 ms	445804 KB	Output is correct
62	Correct	2447 ms	443752 KB	Output is correct
63	Correct	2487 ms	445032 KB	Output is correct
64	Execution timed out	5062 ms	453388 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-