Submission #777671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
777671	2023-07-09T12:45:41 Z	Sam_a17	New Home (APIO18_new_home)	C++17	22 / 100	5000 ms	403380 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;
bool oki = 1;
 
struct node {
  int x, t, a, b;
};
 
vector<node> cand;

struct segTreeMax {  // Range Queries
  vector<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].push_back(v);
        sort(all(mt[x]));
      } else {
        vector<int> new_v;
        int ok = 0;
        for(auto i: mt[x]) {
          if(i == -v && !ok) {
            ok = 1;
          } else {
            new_v.push_back(i);
          }
        }
        new_v.swap(mt[x]);
      }

      if(!mt[x].empty()) {
        mTree[x + sub] = mt[x].back();
      } 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;

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

  {
    vector<node> vi;
    cand.swap(vi);
  }

  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:448:13: warning: unused variable 'mid1' [-Wunused-variable]
  448 |         int mid1 = (it_next->first + j.first + 1) / 2;
      |             ^~~~
new_home.cpp:449:13: warning: unused variable 'mid2' [-Wunused-variable]
  449 |         int mid2 = (it_prev->first + j.first + 1) / 2;
      |             ^~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	239852 KB	Output is correct
2	Correct	98 ms	239740 KB	Output is correct
3	Correct	110 ms	239840 KB	Output is correct
4	Correct	103 ms	239860 KB	Output is correct
5	Correct	104 ms	240088 KB	Output is correct
6	Correct	105 ms	239920 KB	Output is correct
7	Correct	100 ms	239948 KB	Output is correct
8	Correct	100 ms	239936 KB	Output is correct
9	Correct	101 ms	240052 KB	Output is correct
10	Correct	105 ms	240040 KB	Output is correct
11	Correct	102 ms	239972 KB	Output is correct
12	Correct	99 ms	239888 KB	Output is correct
13	Correct	98 ms	239944 KB	Output is correct
14	Correct	99 ms	239952 KB	Output is correct
15	Correct	100 ms	239976 KB	Output is correct
16	Correct	100 ms	240056 KB	Output is correct
17	Correct	100 ms	239960 KB	Output is correct
18	Correct	101 ms	240056 KB	Output is correct
19	Correct	100 ms	240024 KB	Output is correct
20	Correct	104 ms	240112 KB	Output is correct
21	Correct	99 ms	240004 KB	Output is correct
22	Correct	99 ms	240008 KB	Output is correct
23	Correct	100 ms	240000 KB	Output is correct
24	Correct	100 ms	240028 KB	Output is correct
25	Correct	108 ms	240056 KB	Output is correct
26	Correct	102 ms	239988 KB	Output is correct
27	Correct	100 ms	239884 KB	Output is correct
28	Correct	101 ms	239980 KB	Output is correct
29	Correct	100 ms	239972 KB	Output is correct
30	Correct	100 ms	239928 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	239852 KB	Output is correct
2	Correct	98 ms	239740 KB	Output is correct
3	Correct	110 ms	239840 KB	Output is correct
4	Correct	103 ms	239860 KB	Output is correct
5	Correct	104 ms	240088 KB	Output is correct
6	Correct	105 ms	239920 KB	Output is correct
7	Correct	100 ms	239948 KB	Output is correct
8	Correct	100 ms	239936 KB	Output is correct
9	Correct	101 ms	240052 KB	Output is correct
10	Correct	105 ms	240040 KB	Output is correct
11	Correct	102 ms	239972 KB	Output is correct
12	Correct	99 ms	239888 KB	Output is correct
13	Correct	98 ms	239944 KB	Output is correct
14	Correct	99 ms	239952 KB	Output is correct
15	Correct	100 ms	239976 KB	Output is correct
16	Correct	100 ms	240056 KB	Output is correct
17	Correct	100 ms	239960 KB	Output is correct
18	Correct	101 ms	240056 KB	Output is correct
19	Correct	100 ms	240024 KB	Output is correct
20	Correct	104 ms	240112 KB	Output is correct
21	Correct	99 ms	240004 KB	Output is correct
22	Correct	99 ms	240008 KB	Output is correct
23	Correct	100 ms	240000 KB	Output is correct
24	Correct	100 ms	240028 KB	Output is correct
25	Correct	108 ms	240056 KB	Output is correct
26	Correct	102 ms	239988 KB	Output is correct
27	Correct	100 ms	239884 KB	Output is correct
28	Correct	101 ms	239980 KB	Output is correct
29	Correct	100 ms	239972 KB	Output is correct
30	Correct	100 ms	239928 KB	Output is correct
31	Correct	814 ms	266744 KB	Output is correct
32	Correct	144 ms	245396 KB	Output is correct
33	Correct	716 ms	261640 KB	Output is correct
34	Correct	801 ms	262252 KB	Output is correct
35	Correct	796 ms	266304 KB	Output is correct
36	Correct	800 ms	266056 KB	Output is correct
37	Correct	583 ms	259240 KB	Output is correct
38	Correct	582 ms	259088 KB	Output is correct
39	Correct	507 ms	258844 KB	Output is correct
40	Correct	508 ms	258496 KB	Output is correct
41	Correct	644 ms	263296 KB	Output is correct
42	Correct	748 ms	263108 KB	Output is correct
43	Correct	142 ms	246336 KB	Output is correct
44	Correct	633 ms	263388 KB	Output is correct
45	Correct	631 ms	263384 KB	Output is correct
46	Correct	648 ms	263464 KB	Output is correct
47	Correct	450 ms	262896 KB	Output is correct
48	Correct	402 ms	262632 KB	Output is correct
49	Correct	451 ms	262880 KB	Output is correct
50	Correct	466 ms	263280 KB	Output is correct
51	Correct	456 ms	262880 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4347 ms	395780 KB	Output is correct
2	Correct	4597 ms	377504 KB	Output is correct
3	Correct	2961 ms	397504 KB	Output is correct
4	Correct	4147 ms	402788 KB	Output is correct
5	Correct	4285 ms	376952 KB	Output is correct
6	Correct	4496 ms	377396 KB	Output is correct
7	Correct	2779 ms	397432 KB	Output is correct
8	Correct	3147 ms	403380 KB	Output is correct
9	Correct	3374 ms	389080 KB	Output is correct
10	Correct	3770 ms	378308 KB	Output is correct
11	Correct	2260 ms	376688 KB	Output is correct
12	Correct	2419 ms	377884 KB	Output is correct

Subtask #4

0 / 23.0

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

Subtask #5

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	239852 KB	Output is correct
2	Correct	98 ms	239740 KB	Output is correct
3	Correct	110 ms	239840 KB	Output is correct
4	Correct	103 ms	239860 KB	Output is correct
5	Correct	104 ms	240088 KB	Output is correct
6	Correct	105 ms	239920 KB	Output is correct
7	Correct	100 ms	239948 KB	Output is correct
8	Correct	100 ms	239936 KB	Output is correct
9	Correct	101 ms	240052 KB	Output is correct
10	Correct	105 ms	240040 KB	Output is correct
11	Correct	102 ms	239972 KB	Output is correct
12	Correct	99 ms	239888 KB	Output is correct
13	Correct	98 ms	239944 KB	Output is correct
14	Correct	99 ms	239952 KB	Output is correct
15	Correct	100 ms	239976 KB	Output is correct
16	Correct	100 ms	240056 KB	Output is correct
17	Correct	100 ms	239960 KB	Output is correct
18	Correct	101 ms	240056 KB	Output is correct
19	Correct	100 ms	240024 KB	Output is correct
20	Correct	104 ms	240112 KB	Output is correct
21	Correct	99 ms	240004 KB	Output is correct
22	Correct	99 ms	240008 KB	Output is correct
23	Correct	100 ms	240000 KB	Output is correct
24	Correct	100 ms	240028 KB	Output is correct
25	Correct	108 ms	240056 KB	Output is correct
26	Correct	102 ms	239988 KB	Output is correct
27	Correct	100 ms	239884 KB	Output is correct
28	Correct	101 ms	239980 KB	Output is correct
29	Correct	100 ms	239972 KB	Output is correct
30	Correct	100 ms	239928 KB	Output is correct
31	Correct	814 ms	266744 KB	Output is correct
32	Correct	144 ms	245396 KB	Output is correct
33	Correct	716 ms	261640 KB	Output is correct
34	Correct	801 ms	262252 KB	Output is correct
35	Correct	796 ms	266304 KB	Output is correct
36	Correct	800 ms	266056 KB	Output is correct
37	Correct	583 ms	259240 KB	Output is correct
38	Correct	582 ms	259088 KB	Output is correct
39	Correct	507 ms	258844 KB	Output is correct
40	Correct	508 ms	258496 KB	Output is correct
41	Correct	644 ms	263296 KB	Output is correct
42	Correct	748 ms	263108 KB	Output is correct
43	Correct	142 ms	246336 KB	Output is correct
44	Correct	633 ms	263388 KB	Output is correct
45	Correct	631 ms	263384 KB	Output is correct
46	Correct	648 ms	263464 KB	Output is correct
47	Correct	450 ms	262896 KB	Output is correct
48	Correct	402 ms	262632 KB	Output is correct
49	Correct	451 ms	262880 KB	Output is correct
50	Correct	466 ms	263280 KB	Output is correct
51	Correct	456 ms	262880 KB	Output is correct
52	Correct	599 ms	276360 KB	Output is correct
53	Correct	577 ms	271268 KB	Output is correct
54	Correct	729 ms	270808 KB	Output is correct
55	Correct	635 ms	267956 KB	Output is correct
56	Correct	598 ms	270220 KB	Output is correct
57	Correct	656 ms	264992 KB	Output is correct
58	Correct	617 ms	267324 KB	Output is correct
59	Correct	623 ms	269536 KB	Output is correct
60	Correct	630 ms	264460 KB	Output is correct
61	Execution timed out	5067 ms	255284 KB	Time limit exceeded
62	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	239852 KB	Output is correct
2	Correct	98 ms	239740 KB	Output is correct
3	Correct	110 ms	239840 KB	Output is correct
4	Correct	103 ms	239860 KB	Output is correct
5	Correct	104 ms	240088 KB	Output is correct
6	Correct	105 ms	239920 KB	Output is correct
7	Correct	100 ms	239948 KB	Output is correct
8	Correct	100 ms	239936 KB	Output is correct
9	Correct	101 ms	240052 KB	Output is correct
10	Correct	105 ms	240040 KB	Output is correct
11	Correct	102 ms	239972 KB	Output is correct
12	Correct	99 ms	239888 KB	Output is correct
13	Correct	98 ms	239944 KB	Output is correct
14	Correct	99 ms	239952 KB	Output is correct
15	Correct	100 ms	239976 KB	Output is correct
16	Correct	100 ms	240056 KB	Output is correct
17	Correct	100 ms	239960 KB	Output is correct
18	Correct	101 ms	240056 KB	Output is correct
19	Correct	100 ms	240024 KB	Output is correct
20	Correct	104 ms	240112 KB	Output is correct
21	Correct	99 ms	240004 KB	Output is correct
22	Correct	99 ms	240008 KB	Output is correct
23	Correct	100 ms	240000 KB	Output is correct
24	Correct	100 ms	240028 KB	Output is correct
25	Correct	108 ms	240056 KB	Output is correct
26	Correct	102 ms	239988 KB	Output is correct
27	Correct	100 ms	239884 KB	Output is correct
28	Correct	101 ms	239980 KB	Output is correct
29	Correct	100 ms	239972 KB	Output is correct
30	Correct	100 ms	239928 KB	Output is correct
31	Correct	814 ms	266744 KB	Output is correct
32	Correct	144 ms	245396 KB	Output is correct
33	Correct	716 ms	261640 KB	Output is correct
34	Correct	801 ms	262252 KB	Output is correct
35	Correct	796 ms	266304 KB	Output is correct
36	Correct	800 ms	266056 KB	Output is correct
37	Correct	583 ms	259240 KB	Output is correct
38	Correct	582 ms	259088 KB	Output is correct
39	Correct	507 ms	258844 KB	Output is correct
40	Correct	508 ms	258496 KB	Output is correct
41	Correct	644 ms	263296 KB	Output is correct
42	Correct	748 ms	263108 KB	Output is correct
43	Correct	142 ms	246336 KB	Output is correct
44	Correct	633 ms	263388 KB	Output is correct
45	Correct	631 ms	263384 KB	Output is correct
46	Correct	648 ms	263464 KB	Output is correct
47	Correct	450 ms	262896 KB	Output is correct
48	Correct	402 ms	262632 KB	Output is correct
49	Correct	451 ms	262880 KB	Output is correct
50	Correct	466 ms	263280 KB	Output is correct
51	Correct	456 ms	262880 KB	Output is correct
52	Correct	4347 ms	395780 KB	Output is correct
53	Correct	4597 ms	377504 KB	Output is correct
54	Correct	2961 ms	397504 KB	Output is correct
55	Correct	4147 ms	402788 KB	Output is correct
56	Correct	4285 ms	376952 KB	Output is correct
57	Correct	4496 ms	377396 KB	Output is correct
58	Correct	2779 ms	397432 KB	Output is correct
59	Correct	3147 ms	403380 KB	Output is correct
60	Correct	3374 ms	389080 KB	Output is correct
61	Correct	3770 ms	378308 KB	Output is correct
62	Correct	2260 ms	376688 KB	Output is correct
63	Correct	2419 ms	377884 KB	Output is correct
64	Execution timed out	5059 ms	388048 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-