oj.uz

Submission #986279

# Submission time Handle Problem Language Result Execution time Memory
986279 2024-05-20T08:25:34 Z vjudge1 Interval Collection (CCO20_day2problem2) C++17
25 / 25
 6453 ms 199712 KB 
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int inf = 1e9 + 9;
const int nmax = 1e6 + 1;

template<typename T>
struct AINT {
   vector<T> aint;
   int n;
   void init(int n_) {
      n = n_;
      aint.resize(n * 2 + 5, T());
   }
   template<class CB> void walk(CB&& cb) { walk(cb, 1, n); }
   template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 1, n); }
   template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) { 
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
      walk(cb, l, r, L, cl, mid);
      walk(cb, l, r, R, mid + 1, cr);
      aint[node].pull(aint[L], aint[R]);
   }
};

namespace DS {
   auto byL = [](pii a, pii b) { return a.first < b.first || (a.first == b.first && a.second > b.second); };
   auto byR = [](pii a, pii b) { return a.second < b.second || (a.second == b.second && a.first > b.first); };
   
   struct segm {
      int l, r;
      segm(): l(-inf * 2), r(inf * 2) {;}
      void pull(const segm& a, const segm& b) { l = max(a.l, b.l); r = min(b.r, a.r); }
   };
   
   AINT<segm> aint;
   vector<int> ans;
   vector<pair<int, segm>> rollback;
   vector<pii> sortL, sortR;
   
   void insert(int l, int r) {
      sortL.emplace_back(sortL.empty()? pii{l, r} : byL(sortL.back(), pii{l, r})? pii{l, r} : sortL.back());
      sortR.emplace_back(sortR.empty()? pii{l, r} : !byR(sortR.back(), pii{l, r})? pii{l, r} : sortR.back());
      sortL.emplace_back(sortL.back());
      sortR.emplace_back(sortR.back());
      
      ans.push_back(ans.empty()? inf : ans.back());
      aint.walk([&](segm& val, int cl, int cr) {
         ans.back() = min(ans.back(), r - val.l); return 0;
      }, 1, l);
      aint.walk([&](segm& val, int cl, int cr) {
         ans.back() = min(ans.back(), val.r - l); return 0;
      }, r, nmax);
      
      aint.walk([&](segm& val, int cl, int cr) {
         rollback.emplace_back(cl, val);
         val.r = min(val.r, r);
         return 0;
      }, l, l);
      aint.walk([&](segm& val, int cl, int cr) {
         rollback.emplace_back(cl, val);
         ans.emplace_back(ans.back());
         val.l = max(val.l, l);
         return 0;
      }, r, r);
      
      assert(ans.size() == rollback.size());
   }
   
   int time() { return sz(rollback); }
   void pop() {
      aint.walk([&](segm& val, int cl, int cr) {
         val = rollback.back().second;
         return 0;
      }, rollback.back().first, rollback.back().first);
      
      ans.pop_back();
      sortL.pop_back();
      sortR.pop_back();
      rollback.pop_back();
   }
   
   int query() {
      
      //for(auto [a, b] : sortL) cerr << a << ' ' << b << '\t';
      //cerr << "--\n";
      
      if(ans.empty() || ans.back() >= nmax + 5) {
         auto a = sortL.back(), b = sortR.back();
         return max(b.second, a.second) - min(b.first, a.first);
      }
      return ans.back();
   }
}


int started = 0;

struct memory {
   vector<pii> values;
   int enter_time;
   void pull(const memory& a, const memory& b) {
      if(!started) return;
      while(DS::time() > enter_time) DS::pop();
   }
};

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   
   map<pii, vector<int>> still;
   vector<pii> segms;
   vector<pii> times;
   for(int i = 1; i <= n; i++) {
      char ch;
      cin >> ch;
      if(ch == 'A') {
         int l, r;
         cin >> l >> r;
         segms.emplace_back(l, r);
         times.emplace_back(i, n);
         still[pii{l, r}].emplace_back(sz(segms) - 1);
      }
      else {
         int l, r;
         cin >> l >> r;
         auto t = still[pii{l, r}].back();
         still[pii{l, r}].pop_back();
         times[t].second = i - 1;
      }
   }
   
   
   AINT<memory> foroper;
   foroper.init(n);
   
   DS::aint.init(nmax);
   DS::sortL.reserve(nmax);
   DS::ans.reserve(nmax);
   DS::rollback.reserve(nmax);
   DS::sortR.reserve(nmax);
   
   for(int i = 0; i < sz(segms); i++) {
      foroper.walk([&](memory& val, int cl, int cr) {
         val.values.emplace_back(segms[i]);
         return 0;
      }, times[i].first, times[i].second);
   }
   
   started = 1;
   foroper.walk([&](memory& val, int cl, int cr) {
      val.enter_time = DS::time();
      for(auto [a, b] : val.values) DS::insert(a, b);
      
      if(cl != cr) return 1;
      cout << DS::query() << '\n';
      
      while(DS::time() > val.enter_time) DS::pop();
      return 0;
   });
   
   return 0;
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16220 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 4 ms 16216 KB Output is correct
4 Correct 4 ms 16128 KB Output is correct
5 Correct 6 ms 16216 KB Output is correct
6 Correct 5 ms 16220 KB Output is correct
7 Correct 5 ms 16104 KB Output is correct
8 Correct 5 ms 16472 KB Output is correct
9 Correct 5 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 6 ms 16220 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 6 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16220 KB Output is correct
16 Correct 6 ms 16180 KB Output is correct
17 Correct 6 ms 16220 KB Output is correct
18 Correct 6 ms 16220 KB Output is correct
19 Correct 5 ms 16220 KB Output is correct
20 Correct 4 ms 16248 KB Output is correct
21 Correct 6 ms 16416 KB Output is correct
22 Correct 5 ms 16220 KB Output is correct
23 Correct 4 ms 16220 KB Output is correct
24 Correct 4 ms 16220 KB Output is correct
25 Correct 6 ms 16280 KB Output is correct
26 Correct 6 ms 16220 KB Output is correct
27 Correct 6 ms 16220 KB Output is correct
28 Correct 6 ms 16220 KB Output is correct
29 Correct 6 ms 16220 KB Output is correct
30 Correct 7 ms 16220 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 6 ms 16220 KB Output is correct
33 Correct 4 ms 16220 KB Output is correct
34 Correct 4 ms 16220 KB Output is correct
35 Correct 4 ms 16220 KB Output is correct
36 Correct 4 ms 16220 KB Output is correct
37 Correct 5 ms 16220 KB Output is correct
38 Correct 5 ms 16220 KB Output is correct
39 Correct 4 ms 16220 KB Output is correct
40 Correct 5 ms 16220 KB Output is correct
41 Correct 6 ms 16220 KB Output is correct
42 Correct 5 ms 16220 KB Output is correct
43 Correct 5 ms 16220 KB Output is correct
44 Correct 5 ms 16216 KB Output is correct
45 Correct 6 ms 16248 KB Output is correct
46 Correct 5 ms 16220 KB Output is correct
47 Correct 4 ms 16216 KB Output is correct
48 Correct 4 ms 16216 KB Output is correct
49 Correct 4 ms 16220 KB Output is correct
50 Correct 4 ms 16220 KB Output is correct
51 Correct 5 ms 16220 KB Output is correct
52 Correct 5 ms 16220 KB Output is correct
53 Correct 4 ms 16220 KB Output is correct
54 Correct 5 ms 16220 KB Output is correct
55 Correct 5 ms 16220 KB Output is correct
56 Correct 5 ms 16220 KB Output is correct
57 Correct 4 ms 16220 KB Output is correct
58 Correct 5 ms 16220 KB Output is correct
59 Correct 6 ms 16220 KB Output is correct
60 Correct 6 ms 16220 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16220 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 4 ms 16216 KB Output is correct
4 Correct 4 ms 16128 KB Output is correct
5 Correct 6 ms 16216 KB Output is correct
6 Correct 5 ms 16220 KB Output is correct
7 Correct 5 ms 16104 KB Output is correct
8 Correct 5 ms 16472 KB Output is correct
9 Correct 5 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 6 ms 16220 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 6 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16220 KB Output is correct
16 Correct 6 ms 16180 KB Output is correct
17 Correct 6 ms 16220 KB Output is correct
18 Correct 6 ms 16220 KB Output is correct
19 Correct 5 ms 16220 KB Output is correct
20 Correct 4 ms 16248 KB Output is correct
21 Correct 6 ms 16416 KB Output is correct
22 Correct 5 ms 16220 KB Output is correct
23 Correct 4 ms 16220 KB Output is correct
24 Correct 4 ms 16220 KB Output is correct
25 Correct 6 ms 16280 KB Output is correct
26 Correct 6 ms 16220 KB Output is correct
27 Correct 6 ms 16220 KB Output is correct
28 Correct 6 ms 16220 KB Output is correct
29 Correct 6 ms 16220 KB Output is correct
30 Correct 7 ms 16220 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 6 ms 16220 KB Output is correct
33 Correct 4 ms 16220 KB Output is correct
34 Correct 4 ms 16220 KB Output is correct
35 Correct 4 ms 16220 KB Output is correct
36 Correct 4 ms 16220 KB Output is correct
37 Correct 5 ms 16220 KB Output is correct
38 Correct 5 ms 16220 KB Output is correct
39 Correct 4 ms 16220 KB Output is correct
40 Correct 5 ms 16220 KB Output is correct
41 Correct 6 ms 16220 KB Output is correct
42 Correct 5 ms 16220 KB Output is correct
43 Correct 5 ms 16220 KB Output is correct
44 Correct 5 ms 16216 KB Output is correct
45 Correct 6 ms 16248 KB Output is correct
46 Correct 5 ms 16220 KB Output is correct
47 Correct 4 ms 16216 KB Output is correct
48 Correct 4 ms 16216 KB Output is correct
49 Correct 4 ms 16220 KB Output is correct
50 Correct 4 ms 16220 KB Output is correct
51 Correct 5 ms 16220 KB Output is correct
52 Correct 5 ms 16220 KB Output is correct
53 Correct 4 ms 16220 KB Output is correct
54 Correct 5 ms 16220 KB Output is correct
55 Correct 5 ms 16220 KB Output is correct
56 Correct 5 ms 16220 KB Output is correct
57 Correct 4 ms 16220 KB Output is correct
58 Correct 5 ms 16220 KB Output is correct
59 Correct 6 ms 16220 KB Output is correct
60 Correct 6 ms 16220 KB Output is correct
61 Correct 3 ms 15964 KB Output is correct
62 Correct 3 ms 15964 KB Output is correct
63 Correct 4 ms 15964 KB Output is correct
64 Correct 100 ms 19536 KB Output is correct
65 Correct 77 ms 18780 KB Output is correct
66 Correct 62 ms 18520 KB Output is correct
67 Correct 22 ms 18012 KB Output is correct
68 Correct 105 ms 19804 KB Output is correct
69 Correct 83 ms 18780 KB Output is correct
70 Correct 64 ms 18524 KB Output is correct
71 Correct 47 ms 18360 KB Output is correct
72 Correct 107 ms 21976 KB Output is correct
73 Correct 95 ms 19792 KB Output is correct
74 Correct 101 ms 19544 KB Output is correct
75 Correct 92 ms 19500 KB Output is correct
76 Correct 107 ms 20304 KB Output is correct
77 Correct 105 ms 22096 KB Output is correct
78 Correct 103 ms 22148 KB Output is correct
79 Correct 104 ms 20048 KB Output is correct
80 Correct 95 ms 19548 KB Output is correct
81 Correct 77 ms 20884 KB Output is correct
82 Correct 57 ms 18520 KB Output is correct
83 Correct 22 ms 18008 KB Output is correct
84 Correct 97 ms 19540 KB Output is correct
85 Correct 83 ms 18808 KB Output is correct
86 Correct 64 ms 18520 KB Output is correct
87 Correct 50 ms 18268 KB Output is correct
88 Correct 104 ms 21840 KB Output is correct
89 Correct 100 ms 21888 KB Output is correct
90 Correct 91 ms 21504 KB Output is correct
91 Correct 92 ms 19540 KB Output is correct
92 Correct 109 ms 20060 KB Output is correct
93 Correct 101 ms 20048 KB Output is correct
94 Correct 104 ms 20088 KB Output is correct
95 Correct 103 ms 22100 KB Output is correct
96 Correct 22 ms 18044 KB Output is correct
97 Correct 21 ms 18008 KB Output is correct
98 Correct 21 ms 18012 KB Output is correct
99 Correct 22 ms 18012 KB Output is correct
100 Correct 58 ms 18404 KB Output is correct
101 Correct 40 ms 18264 KB Output is correct
102 Correct 46 ms 18368 KB Output is correct
103 Correct 23 ms 18008 KB Output is correct
104 Correct 93 ms 19408 KB Output is correct
105 Correct 76 ms 18964 KB Output is correct
106 Correct 52 ms 18264 KB Output is correct
107 Correct 23 ms 18008 KB Output is correct
108 Correct 96 ms 19024 KB Output is correct
109 Correct 74 ms 18612 KB Output is correct
110 Correct 54 ms 18372 KB Output is correct
111 Correct 23 ms 18008 KB Output is correct
112 Correct 50 ms 19028 KB Output is correct
113 Correct 56 ms 18912 KB Output is correct
114 Correct 49 ms 19024 KB Output is correct
115 Correct 55 ms 19092 KB Output is correct
116 Correct 54 ms 19288 KB Output is correct
117 Correct 55 ms 19028 KB Output is correct
118 Correct 50 ms 20876 KB Output is correct
119 Correct 56 ms 19024 KB Output is correct
120 Correct 49 ms 20992 KB Output is correct
121 Correct 56 ms 19024 KB Output is correct
122 Correct 87 ms 20088 KB Output is correct
123 Correct 83 ms 20088 KB Output is correct
124 Correct 67 ms 18524 KB Output is correct
125 Correct 56 ms 20328 KB Output is correct
126 Correct 54 ms 17956 KB Output is correct
127 Correct 69 ms 18776 KB Output is correct
128 Correct 57 ms 18256 KB Output is correct
129 Correct 52 ms 18168 KB Output is correct
130 Correct 73 ms 18772 KB Output is correct
131 Correct 56 ms 18280 KB Output is correct
132 Correct 54 ms 18008 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16220 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 4 ms 16216 KB Output is correct
4 Correct 4 ms 16128 KB Output is correct
5 Correct 6 ms 16216 KB Output is correct
6 Correct 5 ms 16220 KB Output is correct
7 Correct 5 ms 16104 KB Output is correct
8 Correct 5 ms 16472 KB Output is correct
9 Correct 5 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 6 ms 16220 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 6 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16220 KB Output is correct
16 Correct 6 ms 16180 KB Output is correct
17 Correct 6 ms 16220 KB Output is correct
18 Correct 6 ms 16220 KB Output is correct
19 Correct 5 ms 16220 KB Output is correct
20 Correct 4 ms 16248 KB Output is correct
21 Correct 6 ms 16416 KB Output is correct
22 Correct 5 ms 16220 KB Output is correct
23 Correct 4 ms 16220 KB Output is correct
24 Correct 4 ms 16220 KB Output is correct
25 Correct 6 ms 16280 KB Output is correct
26 Correct 6 ms 16220 KB Output is correct
27 Correct 6 ms 16220 KB Output is correct
28 Correct 6 ms 16220 KB Output is correct
29 Correct 6 ms 16220 KB Output is correct
30 Correct 7 ms 16220 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 6 ms 16220 KB Output is correct
33 Correct 4 ms 16220 KB Output is correct
34 Correct 4 ms 16220 KB Output is correct
35 Correct 4 ms 16220 KB Output is correct
36 Correct 4 ms 16220 KB Output is correct
37 Correct 5 ms 16220 KB Output is correct
38 Correct 5 ms 16220 KB Output is correct
39 Correct 4 ms 16220 KB Output is correct
40 Correct 5 ms 16220 KB Output is correct
41 Correct 6 ms 16220 KB Output is correct
42 Correct 5 ms 16220 KB Output is correct
43 Correct 5 ms 16220 KB Output is correct
44 Correct 5 ms 16216 KB Output is correct
45 Correct 6 ms 16248 KB Output is correct
46 Correct 5 ms 16220 KB Output is correct
47 Correct 4 ms 16216 KB Output is correct
48 Correct 4 ms 16216 KB Output is correct
49 Correct 4 ms 16220 KB Output is correct
50 Correct 4 ms 16220 KB Output is correct
51 Correct 5 ms 16220 KB Output is correct
52 Correct 5 ms 16220 KB Output is correct
53 Correct 4 ms 16220 KB Output is correct
54 Correct 5 ms 16220 KB Output is correct
55 Correct 5 ms 16220 KB Output is correct
56 Correct 5 ms 16220 KB Output is correct
57 Correct 4 ms 16220 KB Output is correct
58 Correct 5 ms 16220 KB Output is correct
59 Correct 6 ms 16220 KB Output is correct
60 Correct 6 ms 16220 KB Output is correct
61 Correct 3 ms 15964 KB Output is correct
62 Correct 3 ms 15964 KB Output is correct
63 Correct 4 ms 15964 KB Output is correct
64 Correct 100 ms 19536 KB Output is correct
65 Correct 77 ms 18780 KB Output is correct
66 Correct 62 ms 18520 KB Output is correct
67 Correct 22 ms 18012 KB Output is correct
68 Correct 105 ms 19804 KB Output is correct
69 Correct 83 ms 18780 KB Output is correct
70 Correct 64 ms 18524 KB Output is correct
71 Correct 47 ms 18360 KB Output is correct
72 Correct 107 ms 21976 KB Output is correct
73 Correct 95 ms 19792 KB Output is correct
74 Correct 101 ms 19544 KB Output is correct
75 Correct 92 ms 19500 KB Output is correct
76 Correct 107 ms 20304 KB Output is correct
77 Correct 105 ms 22096 KB Output is correct
78 Correct 103 ms 22148 KB Output is correct
79 Correct 104 ms 20048 KB Output is correct
80 Correct 95 ms 19548 KB Output is correct
81 Correct 77 ms 20884 KB Output is correct
82 Correct 57 ms 18520 KB Output is correct
83 Correct 22 ms 18008 KB Output is correct
84 Correct 97 ms 19540 KB Output is correct
85 Correct 83 ms 18808 KB Output is correct
86 Correct 64 ms 18520 KB Output is correct
87 Correct 50 ms 18268 KB Output is correct
88 Correct 104 ms 21840 KB Output is correct
89 Correct 100 ms 21888 KB Output is correct
90 Correct 91 ms 21504 KB Output is correct
91 Correct 92 ms 19540 KB Output is correct
92 Correct 109 ms 20060 KB Output is correct
93 Correct 101 ms 20048 KB Output is correct
94 Correct 104 ms 20088 KB Output is correct
95 Correct 103 ms 22100 KB Output is correct
96 Correct 22 ms 18044 KB Output is correct
97 Correct 21 ms 18008 KB Output is correct
98 Correct 21 ms 18012 KB Output is correct
99 Correct 22 ms 18012 KB Output is correct
100 Correct 58 ms 18404 KB Output is correct
101 Correct 40 ms 18264 KB Output is correct
102 Correct 46 ms 18368 KB Output is correct
103 Correct 23 ms 18008 KB Output is correct
104 Correct 93 ms 19408 KB Output is correct
105 Correct 76 ms 18964 KB Output is correct
106 Correct 52 ms 18264 KB Output is correct
107 Correct 23 ms 18008 KB Output is correct
108 Correct 96 ms 19024 KB Output is correct
109 Correct 74 ms 18612 KB Output is correct
110 Correct 54 ms 18372 KB Output is correct
111 Correct 23 ms 18008 KB Output is correct
112 Correct 50 ms 19028 KB Output is correct
113 Correct 56 ms 18912 KB Output is correct
114 Correct 49 ms 19024 KB Output is correct
115 Correct 55 ms 19092 KB Output is correct
116 Correct 54 ms 19288 KB Output is correct
117 Correct 55 ms 19028 KB Output is correct
118 Correct 50 ms 20876 KB Output is correct
119 Correct 56 ms 19024 KB Output is correct
120 Correct 49 ms 20992 KB Output is correct
121 Correct 56 ms 19024 KB Output is correct
122 Correct 87 ms 20088 KB Output is correct
123 Correct 83 ms 20088 KB Output is correct
124 Correct 67 ms 18524 KB Output is correct
125 Correct 56 ms 20328 KB Output is correct
126 Correct 54 ms 17956 KB Output is correct
127 Correct 69 ms 18776 KB Output is correct
128 Correct 57 ms 18256 KB Output is correct
129 Correct 52 ms 18168 KB Output is correct
130 Correct 73 ms 18772 KB Output is correct
131 Correct 56 ms 18280 KB Output is correct
132 Correct 54 ms 18008 KB Output is correct
133 Correct 464 ms 31952 KB Output is correct
134 Correct 390 ms 27980 KB Output is correct
135 Correct 293 ms 26772 KB Output is correct
136 Correct 106 ms 24716 KB Output is correct
137 Correct 462 ms 34120 KB Output is correct
138 Correct 416 ms 29980 KB Output is correct
139 Correct 302 ms 26560 KB Output is correct
140 Correct 232 ms 25840 KB Output is correct
141 Correct 527 ms 36420 KB Output is correct
142 Correct 459 ms 33204 KB Output is correct
143 Correct 449 ms 31300 KB Output is correct
144 Correct 462 ms 32776 KB Output is correct
145 Correct 503 ms 36712 KB Output is correct
146 Correct 497 ms 34576 KB Output is correct
147 Correct 506 ms 37504 KB Output is correct
148 Correct 496 ms 35292 KB Output is correct
149 Correct 468 ms 30528 KB Output is correct
150 Correct 383 ms 27724 KB Output is correct
151 Correct 289 ms 26788 KB Output is correct
152 Correct 109 ms 24864 KB Output is correct
153 Correct 468 ms 30404 KB Output is correct
154 Correct 403 ms 27912 KB Output is correct
155 Correct 297 ms 26472 KB Output is correct
156 Correct 224 ms 26108 KB Output is correct
157 Correct 490 ms 33728 KB Output is correct
158 Correct 462 ms 32892 KB Output is correct
159 Correct 439 ms 31548 KB Output is correct
160 Correct 431 ms 31332 KB Output is correct
161 Correct 491 ms 33392 KB Output is correct
162 Correct 494 ms 36748 KB Output is correct
163 Correct 496 ms 36916 KB Output is correct
164 Correct 515 ms 37284 KB Output is correct
165 Correct 82 ms 23880 KB Output is correct
166 Correct 92 ms 24112 KB Output is correct
167 Correct 84 ms 24036 KB Output is correct
168 Correct 86 ms 23884 KB Output is correct
169 Correct 237 ms 25884 KB Output is correct
170 Correct 187 ms 25416 KB Output is correct
171 Correct 176 ms 25256 KB Output is correct
172 Correct 100 ms 24136 KB Output is correct
173 Correct 447 ms 34092 KB Output is correct
174 Correct 363 ms 27344 KB Output is correct
175 Correct 272 ms 26188 KB Output is correct
176 Correct 107 ms 24396 KB Output is correct
177 Correct 461 ms 28500 KB Output is correct
178 Correct 379 ms 27444 KB Output is correct
179 Correct 289 ms 26072 KB Output is correct
180 Correct 108 ms 24380 KB Output is correct
181 Correct 223 ms 28488 KB Output is correct
182 Correct 264 ms 32860 KB Output is correct
183 Correct 214 ms 28480 KB Output is correct
184 Correct 263 ms 28544 KB Output is correct
185 Correct 218 ms 28692 KB Output is correct
186 Correct 267 ms 30324 KB Output is correct
187 Correct 233 ms 32536 KB Output is correct
188 Correct 261 ms 28588 KB Output is correct
189 Correct 221 ms 28700 KB Output is correct
190 Correct 262 ms 30276 KB Output is correct
191 Correct 375 ms 33348 KB Output is correct
192 Correct 373 ms 36780 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 93184 KB Output is correct
2 Correct 1569 ms 92600 KB Output is correct
3 Correct 3270 ms 163772 KB Output is correct
4 Correct 3261 ms 164332 KB Output is correct
5 Correct 4014 ms 190536 KB Output is correct
6 Correct 4097 ms 190572 KB Output is correct
7 Correct 3687 ms 117732 KB Output is correct
8 Correct 2929 ms 100712 KB Output is correct
9 Correct 2851 ms 100700 KB Output is correct
10 Correct 3907 ms 127080 KB Output is correct
11 Correct 2949 ms 100664 KB Output is correct
12 Correct 2805 ms 98536 KB Output is correct
13 Correct 4059 ms 120464 KB Output is correct
14 Correct 2944 ms 100820 KB Output is correct
15 Correct 2813 ms 98396 KB Output is correct
16 Correct 1474 ms 94804 KB Output is correct
17 Correct 1482 ms 94552 KB Output is correct
18 Correct 1502 ms 94660 KB Output is correct
19 Correct 1507 ms 95260 KB Output is correct
20 Correct 1477 ms 94652 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16220 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 4 ms 16216 KB Output is correct
4 Correct 4 ms 16128 KB Output is correct
5 Correct 6 ms 16216 KB Output is correct
6 Correct 5 ms 16220 KB Output is correct
7 Correct 5 ms 16104 KB Output is correct
8 Correct 5 ms 16472 KB Output is correct
9 Correct 5 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 6 ms 16220 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 6 ms 16220 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 6 ms 16220 KB Output is correct
16 Correct 6 ms 16180 KB Output is correct
17 Correct 6 ms 16220 KB Output is correct
18 Correct 6 ms 16220 KB Output is correct
19 Correct 5 ms 16220 KB Output is correct
20 Correct 4 ms 16248 KB Output is correct
21 Correct 6 ms 16416 KB Output is correct
22 Correct 5 ms 16220 KB Output is correct
23 Correct 4 ms 16220 KB Output is correct
24 Correct 4 ms 16220 KB Output is correct
25 Correct 6 ms 16280 KB Output is correct
26 Correct 6 ms 16220 KB Output is correct
27 Correct 6 ms 16220 KB Output is correct
28 Correct 6 ms 16220 KB Output is correct
29 Correct 6 ms 16220 KB Output is correct
30 Correct 7 ms 16220 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 6 ms 16220 KB Output is correct
33 Correct 4 ms 16220 KB Output is correct
34 Correct 4 ms 16220 KB Output is correct
35 Correct 4 ms 16220 KB Output is correct
36 Correct 4 ms 16220 KB Output is correct
37 Correct 5 ms 16220 KB Output is correct
38 Correct 5 ms 16220 KB Output is correct
39 Correct 4 ms 16220 KB Output is correct
40 Correct 5 ms 16220 KB Output is correct
41 Correct 6 ms 16220 KB Output is correct
42 Correct 5 ms 16220 KB Output is correct
43 Correct 5 ms 16220 KB Output is correct
44 Correct 5 ms 16216 KB Output is correct
45 Correct 6 ms 16248 KB Output is correct
46 Correct 5 ms 16220 KB Output is correct
47 Correct 4 ms 16216 KB Output is correct
48 Correct 4 ms 16216 KB Output is correct
49 Correct 4 ms 16220 KB Output is correct
50 Correct 4 ms 16220 KB Output is correct
51 Correct 5 ms 16220 KB Output is correct
52 Correct 5 ms 16220 KB Output is correct
53 Correct 4 ms 16220 KB Output is correct
54 Correct 5 ms 16220 KB Output is correct
55 Correct 5 ms 16220 KB Output is correct
56 Correct 5 ms 16220 KB Output is correct
57 Correct 4 ms 16220 KB Output is correct
58 Correct 5 ms 16220 KB Output is correct
59 Correct 6 ms 16220 KB Output is correct
60 Correct 6 ms 16220 KB Output is correct
61 Correct 3 ms 15964 KB Output is correct
62 Correct 3 ms 15964 KB Output is correct
63 Correct 4 ms 15964 KB Output is correct
64 Correct 100 ms 19536 KB Output is correct
65 Correct 77 ms 18780 KB Output is correct
66 Correct 62 ms 18520 KB Output is correct
67 Correct 22 ms 18012 KB Output is correct
68 Correct 105 ms 19804 KB Output is correct
69 Correct 83 ms 18780 KB Output is correct
70 Correct 64 ms 18524 KB Output is correct
71 Correct 47 ms 18360 KB Output is correct
72 Correct 107 ms 21976 KB Output is correct
73 Correct 95 ms 19792 KB Output is correct
74 Correct 101 ms 19544 KB Output is correct
75 Correct 92 ms 19500 KB Output is correct
76 Correct 107 ms 20304 KB Output is correct
77 Correct 105 ms 22096 KB Output is correct
78 Correct 103 ms 22148 KB Output is correct
79 Correct 104 ms 20048 KB Output is correct
80 Correct 95 ms 19548 KB Output is correct
81 Correct 77 ms 20884 KB Output is correct
82 Correct 57 ms 18520 KB Output is correct
83 Correct 22 ms 18008 KB Output is correct
84 Correct 97 ms 19540 KB Output is correct
85 Correct 83 ms 18808 KB Output is correct
86 Correct 64 ms 18520 KB Output is correct
87 Correct 50 ms 18268 KB Output is correct
88 Correct 104 ms 21840 KB Output is correct
89 Correct 100 ms 21888 KB Output is correct
90 Correct 91 ms 21504 KB Output is correct
91 Correct 92 ms 19540 KB Output is correct
92 Correct 109 ms 20060 KB Output is correct
93 Correct 101 ms 20048 KB Output is correct
94 Correct 104 ms 20088 KB Output is correct
95 Correct 103 ms 22100 KB Output is correct
96 Correct 22 ms 18044 KB Output is correct
97 Correct 21 ms 18008 KB Output is correct
98 Correct 21 ms 18012 KB Output is correct
99 Correct 22 ms 18012 KB Output is correct
100 Correct 58 ms 18404 KB Output is correct
101 Correct 40 ms 18264 KB Output is correct
102 Correct 46 ms 18368 KB Output is correct
103 Correct 23 ms 18008 KB Output is correct
104 Correct 93 ms 19408 KB Output is correct
105 Correct 76 ms 18964 KB Output is correct
106 Correct 52 ms 18264 KB Output is correct
107 Correct 23 ms 18008 KB Output is correct
108 Correct 96 ms 19024 KB Output is correct
109 Correct 74 ms 18612 KB Output is correct
110 Correct 54 ms 18372 KB Output is correct
111 Correct 23 ms 18008 KB Output is correct
112 Correct 50 ms 19028 KB Output is correct
113 Correct 56 ms 18912 KB Output is correct
114 Correct 49 ms 19024 KB Output is correct
115 Correct 55 ms 19092 KB Output is correct
116 Correct 54 ms 19288 KB Output is correct
117 Correct 55 ms 19028 KB Output is correct
118 Correct 50 ms 20876 KB Output is correct
119 Correct 56 ms 19024 KB Output is correct
120 Correct 49 ms 20992 KB Output is correct
121 Correct 56 ms 19024 KB Output is correct
122 Correct 87 ms 20088 KB Output is correct
123 Correct 83 ms 20088 KB Output is correct
124 Correct 67 ms 18524 KB Output is correct
125 Correct 56 ms 20328 KB Output is correct
126 Correct 54 ms 17956 KB Output is correct
127 Correct 69 ms 18776 KB Output is correct
128 Correct 57 ms 18256 KB Output is correct
129 Correct 52 ms 18168 KB Output is correct
130 Correct 73 ms 18772 KB Output is correct
131 Correct 56 ms 18280 KB Output is correct
132 Correct 54 ms 18008 KB Output is correct
133 Correct 464 ms 31952 KB Output is correct
134 Correct 390 ms 27980 KB Output is correct
135 Correct 293 ms 26772 KB Output is correct
136 Correct 106 ms 24716 KB Output is correct
137 Correct 462 ms 34120 KB Output is correct
138 Correct 416 ms 29980 KB Output is correct
139 Correct 302 ms 26560 KB Output is correct
140 Correct 232 ms 25840 KB Output is correct
141 Correct 527 ms 36420 KB Output is correct
142 Correct 459 ms 33204 KB Output is correct
143 Correct 449 ms 31300 KB Output is correct
144 Correct 462 ms 32776 KB Output is correct
145 Correct 503 ms 36712 KB Output is correct
146 Correct 497 ms 34576 KB Output is correct
147 Correct 506 ms 37504 KB Output is correct
148 Correct 496 ms 35292 KB Output is correct
149 Correct 468 ms 30528 KB Output is correct
150 Correct 383 ms 27724 KB Output is correct
151 Correct 289 ms 26788 KB Output is correct
152 Correct 109 ms 24864 KB Output is correct
153 Correct 468 ms 30404 KB Output is correct
154 Correct 403 ms 27912 KB Output is correct
155 Correct 297 ms 26472 KB Output is correct
156 Correct 224 ms 26108 KB Output is correct
157 Correct 490 ms 33728 KB Output is correct
158 Correct 462 ms 32892 KB Output is correct
159 Correct 439 ms 31548 KB Output is correct
160 Correct 431 ms 31332 KB Output is correct
161 Correct 491 ms 33392 KB Output is correct
162 Correct 494 ms 36748 KB Output is correct
163 Correct 496 ms 36916 KB Output is correct
164 Correct 515 ms 37284 KB Output is correct
165 Correct 82 ms 23880 KB Output is correct
166 Correct 92 ms 24112 KB Output is correct
167 Correct 84 ms 24036 KB Output is correct
168 Correct 86 ms 23884 KB Output is correct
169 Correct 237 ms 25884 KB Output is correct
170 Correct 187 ms 25416 KB Output is correct
171 Correct 176 ms 25256 KB Output is correct
172 Correct 100 ms 24136 KB Output is correct
173 Correct 447 ms 34092 KB Output is correct
174 Correct 363 ms 27344 KB Output is correct
175 Correct 272 ms 26188 KB Output is correct
176 Correct 107 ms 24396 KB Output is correct
177 Correct 461 ms 28500 KB Output is correct
178 Correct 379 ms 27444 KB Output is correct
179 Correct 289 ms 26072 KB Output is correct
180 Correct 108 ms 24380 KB Output is correct
181 Correct 223 ms 28488 KB Output is correct
182 Correct 264 ms 32860 KB Output is correct
183 Correct 214 ms 28480 KB Output is correct
184 Correct 263 ms 28544 KB Output is correct
185 Correct 218 ms 28692 KB Output is correct
186 Correct 267 ms 30324 KB Output is correct
187 Correct 233 ms 32536 KB Output is correct
188 Correct 261 ms 28588 KB Output is correct
189 Correct 221 ms 28700 KB Output is correct
190 Correct 262 ms 30276 KB Output is correct
191 Correct 375 ms 33348 KB Output is correct
192 Correct 373 ms 36780 KB Output is correct
193 Correct 1572 ms 93184 KB Output is correct
194 Correct 1569 ms 92600 KB Output is correct
195 Correct 3270 ms 163772 KB Output is correct
196 Correct 3261 ms 164332 KB Output is correct
197 Correct 4014 ms 190536 KB Output is correct
198 Correct 4097 ms 190572 KB Output is correct
199 Correct 3687 ms 117732 KB Output is correct
200 Correct 2929 ms 100712 KB Output is correct
201 Correct 2851 ms 100700 KB Output is correct
202 Correct 3907 ms 127080 KB Output is correct
203 Correct 2949 ms 100664 KB Output is correct
204 Correct 2805 ms 98536 KB Output is correct
205 Correct 4059 ms 120464 KB Output is correct
206 Correct 2944 ms 100820 KB Output is correct
207 Correct 2813 ms 98396 KB Output is correct
208 Correct 1474 ms 94804 KB Output is correct
209 Correct 1482 ms 94552 KB Output is correct
210 Correct 1502 ms 94660 KB Output is correct
211 Correct 1507 ms 95260 KB Output is correct
212 Correct 1477 ms 94652 KB Output is correct
213 Correct 6291 ms 166964 KB Output is correct
214 Correct 5334 ms 142988 KB Output is correct
215 Correct 4192 ms 133120 KB Output is correct
216 Correct 1851 ms 118272 KB Output is correct
217 Correct 6136 ms 176744 KB Output is correct
218 Correct 5289 ms 148016 KB Output is correct
219 Correct 4155 ms 136540 KB Output is correct
220 Correct 2497 ms 122320 KB Output is correct
221 Correct 6410 ms 193076 KB Output is correct
222 Correct 6113 ms 185948 KB Output is correct
223 Correct 5997 ms 184732 KB Output is correct
224 Correct 5831 ms 183344 KB Output is correct
225 Correct 6453 ms 199056 KB Output is correct
226 Correct 6270 ms 199344 KB Output is correct
227 Correct 6333 ms 199288 KB Output is correct
228 Correct 6311 ms 199476 KB Output is correct
229 Correct 6158 ms 174804 KB Output is correct
230 Correct 5148 ms 144800 KB Output is correct
231 Correct 4075 ms 132896 KB Output is correct
232 Correct 1873 ms 118060 KB Output is correct
233 Correct 6064 ms 176040 KB Output is correct
234 Correct 5207 ms 151500 KB Output is correct
235 Correct 4074 ms 134352 KB Output is correct
236 Correct 2599 ms 123348 KB Output is correct
237 Correct 6169 ms 190804 KB Output is correct
238 Correct 5891 ms 186412 KB Output is correct
239 Correct 5703 ms 183220 KB Output is correct
240 Correct 5708 ms 183248 KB Output is correct
241 Correct 6222 ms 199712 KB Output is correct
242 Correct 6227 ms 198888 KB Output is correct
243 Correct 6199 ms 199172 KB Output is correct
244 Correct 6169 ms 198772 KB Output is correct
245 Correct 891 ms 103400 KB Output is correct
246 Correct 882 ms 103248 KB Output is correct
247 Correct 884 ms 103256 KB Output is correct
248 Correct 869 ms 103576 KB Output is correct
249 Correct 2307 ms 120452 KB Output is correct
250 Correct 2470 ms 122016 KB Output is correct
251 Correct 2618 ms 122924 KB Output is correct
252 Correct 1487 ms 112056 KB Output is correct
253 Correct 5861 ms 172308 KB Output is correct
254 Correct 4944 ms 148304 KB Output is correct
255 Correct 3870 ms 131964 KB Output is correct
256 Correct 1753 ms 112992 KB Output is correct
257 Correct 6120 ms 155016 KB Output is correct
258 Correct 5002 ms 136892 KB Output is correct
259 Correct 3944 ms 125484 KB Output is correct
260 Correct 1795 ms 111864 KB Output is correct
261 Correct 2571 ms 156136 KB Output is correct
262 Correct 3654 ms 152724 KB Output is correct
263 Correct 2388 ms 141100 KB Output is correct
264 Correct 3379 ms 140168 KB Output is correct
265 Correct 2567 ms 152684 KB Output is correct
266 Correct 3644 ms 155072 KB Output is correct
267 Correct 2353 ms 140260 KB Output is correct
268 Correct 3420 ms 140272 KB Output is correct
269 Correct 4093 ms 198652 KB Output is correct
270 Correct 4062 ms 198436 KB Output is correct
271 Correct 3782 ms 126168 KB Output is correct
272 Correct 2911 ms 108028 KB Output is correct
273 Correct 4022 ms 135964 KB Output is correct
274 Correct 2979 ms 106392 KB Output is correct
275 Correct 3258 ms 128080 KB Output is correct