oj.uz

Submission #1018107

# Submission time Handle Problem Language Result Execution time Memory
1018107 2024-07-09T14:28:17 Z cadmiumsky Radio Towers (IOI22_towers) C++17
58 / 100
 1524 ms 527192 KB 
#include "towers.h"
 
#include <vector>
#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 nmax = 2e5 + 5;
int v[nmax];
 
namespace DSU {
   int dsu[nmax], nxt[nmax];
   int mxR[nmax];
 
   void init(int l, int r) {
      for(int i = l; i <= r; i++) dsu[i] = i, nxt[i] = i + 1;
      return;
   }
   int f(int x) { return x == dsu[x]? x : dsu[x] = f(dsu[x]); }
   void unite(int x, int y) {
      x = f(x);
      y = f(y);
      if(x == y) return;
      if(x > y) swap(x, y);
      dsu[y] = x;
      mxR[x] = max(mxR[x], mxR[y]);
      nxt[x] = nxt[y];
      return;
   }
   int coef(int i, const vector<int>& p) {
      i = f(i);
      return mxR[i] - max(v[p[i]], v[p[nxt[i]]]);
   }
}
 
int timeout[nmax];
int dir[nmax];
 
void initglobals(signed L, signed R) {
   
   ++L;
   ++R;
   
   vector<int> p;
   for(int i = L; i <= R; i++) {
      if((i == L  || v[i] < v[i - 1]) && (i == R || v[i] < v[i + 1])) p.emplace_back(i), timeout[i] = 1e9 + 5;
      else timeout[i] = 0;
   }
   
   DSU::init(0, sz(p));
   
   set<pii> heap;
   
   set<int> indemnizatii;
   for(int i = 0; i < sz(p) - 1; i++) {
      indemnizatii.emplace(i);
      indemnizatii.emplace(i + 1);
      int mx = v[p[i] + 1];
      for(int j = p[i] + 2; j < p[i + 1]; j++)
         mx = max(mx, v[j]);
      DSU::mxR[i] = mx;
      heap.emplace(mx - max(v[p[i]], v[p[i + 1]]), i);
   }
   
   auto get = [&](int p_) { return pii{DSU::coef(p_, p), p_}; };
      
   while(!heap.empty()) {
      auto [C, i] = *heap.begin();
      heap.erase(heap.begin());
      
      i = DSU::f(i);
      int urm = DSU::nxt[i];
      if(i != *indemnizatii.begin()) {
         int ant = DSU::f(i - 1);
         heap.erase(heap.find(get(ant)));
      }
      if(urm != *indemnizatii.rbegin()) 
         heap.erase(heap.find(get(urm)));
      
      if(v[p[i]] < v[p[urm]]) {
         timeout[p[urm]] = C;
         dir[p[urm]] = p[i];
         DSU::unite(i, urm);
         indemnizatii.erase(urm);
         if(i != *indemnizatii.begin()) {
            int ant = DSU::f(i - 1);
            heap.insert(get(ant));
         }
         if(i != *indemnizatii.rbegin())
            heap.insert(get(i));
         
      }
      else {
         timeout[p[i]] = C;
         dir[p[i]] = p[urm];
         if(i != *indemnizatii.begin()) {
            int ant = DSU::f(i - 1);
            DSU::unite(ant, i);
            heap.insert(get(ant));
         }
         if(urm != *indemnizatii.rbegin())
            heap.insert(get(urm));
         indemnizatii.erase(i);
      }  
   }
}
 
 
template<typename T>
struct AINT {
   struct Node {
      Node *l, *r;
      T inner;
   };
   Node mem[nmax * 36];
   int cnt = 0;
   using ns = Node*;
   
   int n;
   ns root, nil;
   int filled = 0;
   void init(int n_) {
      n = n_;
      nil = newnode(0, 0, T());
      nil -> l = nil;
      nil -> r = nil;
      root = nil;
      root = walk([&](T& inner, int cl, int cr) {
         if(cl != cr) return 1;
         inner = T();
         return 0;
      });
   }
   
   ns newnode(ns L, ns R, T val) {
      mem[cnt++] = (Node{L, R, val});
      return mem + cnt - 1;
   }
   ns newnode() {
      return newnode(nil, nil, T());
   }
   
   template<class CB> ns walk(CB&& cb) { filled ++; return root = walk(cb, 1, n); }
   template<class CB> ns walk(CB&& cb, int l, int r) { return root = walk(cb, l, r, root, 1, n); }
   template<class CB> ns walk(CB&& cb, int l, int r, ns node, int cl, int cr) { 
      if(r < cl || cr < l) return node;
      auto a = node -> inner;
      if(l <= cl && cr <= r && !cb(node -> inner, cl, cr)) { auto rv = newnode(node -> l, node -> r, node -> inner); node -> inner = a;  return rv; }
      int mid = (cl + cr) >> 1;
      auto herenow = newnode();
      herenow -> l = walk(cb, l, r, node -> l, cl, mid);
      herenow -> r = walk(cb, l, r, node -> r, mid + 1, cr);
      //cerr << cl << ' ' << cr << "\t" << herenow -> inner.val << '\t' << herenow -> l -> inner.val << '\t' << herenow -> r -> inner.val << '\n';
      herenow -> inner.pull(herenow -> l -> inner, herenow -> r -> inner);
      return herenow;
   }
   
   
   template<class CB> void const_walk(CB&& cb, ns start) const { return const_walk(cb, start, 1, n); }
   template<class CB> void const_walk(CB&& cb, ns start, int l, int r) const { return const_walk(cb, l, r, start, 1, n); }
   template<class CB> void const_walk(CB&& cb, int l, int r, ns node, int cl, int cr) const { 
      if(r < cl || cr < l) return;
      if(l <= cl && cr <= r && !cb(node -> inner, cl, cr)) return;
      int mid = (cl + cr) >> 1;
      const_walk(cb, l, r, node -> l, cl, mid);
      const_walk(cb, l, r, node -> r, mid + 1, cr);
      return;
   }
};
 
struct Sum {
   int val;
   Sum(int a = 0): val(a) {;}
   void pull(const Sum& L, const Sum& R) { val = L.val + R.val; }
};
 
struct mnidx {
   int val;
   mnidx(int a = 0): val(a) {;}
   void pull(const mnidx& L, const mnidx& R) { val = v[L.val] < v[R.val]? L.val : R.val; }
};
 
struct mxval {
   int val;
   mxval(int a = 0): val(a) {;}
   void pull(const mxval& L, const mxval& R) { val = max(L.val, R.val); }
};
 
map<int, AINT<Sum>::ns> sumroot;
map<int, AINT<mnidx>::ns> raiseroot, fallroot;
 
AINT<Sum> sum_aint;
AINT<mnidx> dir_aint;
AINT<mxval> max_aint;
 
void init(signed N, std::vector<signed> H) {
   //cerr << N << ' ' << sz(H) << '\n';
   v[0] = 1e9 + 2;
   for(int i = 0; i < N; i++) v[i + 1] = H[i]; 
   initglobals(0, N - 1);
   max_aint.init(N);
   max_aint.walk([&](auto &a, int cl, int cr) { if(cl != cr) return 1; a.val = v[cl]; return 0; });
   
 
   vector<int> idx(N); iota(all(idx), 1);
   sum_aint.init(N);
   sort(all(idx), [&](int a, int b) { return timeout[a] > timeout[b]; });
   for(auto x : idx)
      sumroot[timeout[x]] = sum_aint.walk([&](auto& a, int cl, int cr) { a.val = 1; return 0;}, x, x);
      //cerr << timeout[x] << '\t' << sum_aint.root -> inner.val << '\n';
      
   dir_aint.init(N);
   sort(all(idx), [&](int a, int b) { return dir[a] < dir[b]; });
   raiseroot[0] = dir_aint.root;
   for(auto x : idx) 
      raiseroot[dir[x]] = dir_aint.walk([&](auto& a, int cl, int cr) { a.val = cl * (timeout[cl] != 0); return 0; }, x, x); 
   for(int i = 1; i <= N; i++) if(raiseroot.count(i) == 0) raiseroot[i] = raiseroot[i - 1];
   
   dir_aint.init(N);
   sort(all(idx), [&](int a, int b) { return dir[a] > dir[b]; });
   fallroot[N + 1] = dir_aint.root;
   for(auto x : idx) 
      fallroot[dir[x]] = dir_aint.walk([&](auto& a, int cl, int cr) { a.val = cl * (timeout[cl] != 0); return 0; }, x, x); 
   for(int i = N; i > 0; i--) if(fallroot.count(i) == 0) fallroot[i] = fallroot[i + 1];
   
   
   return;
}
 
int query_max(int l, int r) { 
   int mx = 0;
   max_aint.const_walk([&](auto& a, int cl, int cr) { mx = max(mx, a.val); return 0;}, max_aint.root, l, r);
   return mx;
}
 
signed max_towers(signed L, signed R, signed D) {
   ++L, ++R;
   if(sumroot.lower_bound(D) == sumroot.end()) return 1;
   auto forsum = sumroot.lower_bound(D) -> second;
   
   
   int alltogether = 0;
   sum_aint.const_walk([&](auto a, int cl, int cr) { alltogether += a.val; return 0; }, forsum, L, R);
   if(alltogether == 0) {
      int mx = query_max(L, R);
      return mx - max(v[L], v[R]) >= D? 2 : 1;
   }
   
   int l = L, r;
   sum_aint.const_walk([&](auto &a, int cl, int cr) { 
      if(l < cl) return 0; 
      if(a.val == 0) { l = cr + 1; return 0; } 
      if(cl == cr) { l = cl; return 0; } 
      return 1; }, forsum, L, R);
   
   int rez = alltogether;
   
   if(L < l) {
      int mn = L;
      dir_aint.const_walk([&](mnidx& a, int cl, int cr) { if(v[mn] > v[a.val]) mn = a.val; return 0;}, raiseroot[L - 1], L + 1, l - 1);
      int mx = query_max(mn + 1, l);
      
      if(mx - max(v[l], v[mn]) >= D) rez++;
   }
   int limit = alltogether - 1;
   
   r = l;
   sum_aint.const_walk([&](auto &a, int cl, int cr) { 
      if(r < cl) return 0; 
      if(a.val <= limit) { limit -= a.val; r = cr + 1; return 0; } 
      if(cl == cr) { r = cl; return 0; } 
      return 1; }, forsum, l, R);
   
   if(r < R) {
      int mn = R;
      dir_aint.const_walk([&](mnidx& a, int cl, int cr) { if(v[mn] > v[a.val]) mn = a.val; return 0;}, fallroot[R + 1], r + 1, R - 1);
      int mx = query_max(r + 1, mn - 1);
      if(mx - max(v[r], v[mn]) >= D) rez++;
   }
   
   //cerr << L << ' ' << l << ' ' << r << ' ' << R << '\n';
   
   return rez;
}
//#undef int

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 517760 KB Output is correct
2 Correct 966 ms 523344 KB Output is correct
3 Correct 991 ms 523328 KB Output is correct
4 Correct 1010 ms 523400 KB Output is correct
5 Correct 977 ms 523496 KB Output is correct
6 Correct 1016 ms 523600 KB Output is correct
7 Correct 978 ms 523420 KB Output is correct
8 Correct 149 ms 509300 KB Output is correct
9 Correct 147 ms 509684 KB Output is correct
10 Correct 158 ms 509496 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 509336 KB Output is correct
2 Correct 150 ms 509572 KB Output is correct
3 Correct 164 ms 509856 KB Output is correct
4 Correct 145 ms 509776 KB Output is correct
5 Correct 148 ms 509624 KB Output is correct
6 Correct 178 ms 509656 KB Output is correct
7 Correct 146 ms 509624 KB Output is correct
8 Correct 144 ms 509724 KB Output is correct
9 Correct 145 ms 509512 KB Output is correct
10 Correct 150 ms 509596 KB Output is correct
11 Correct 145 ms 509672 KB Output is correct
12 Correct 141 ms 509264 KB Output is correct
13 Correct 151 ms 509676 KB Output is correct
14 Correct 178 ms 509584 KB Output is correct
15 Correct 145 ms 509692 KB Output is correct
16 Correct 147 ms 509560 KB Output is correct
17 Correct 158 ms 509672 KB Output is correct
18 Correct 154 ms 509524 KB Output is correct
19 Correct 150 ms 509516 KB Output is correct
20 Correct 198 ms 509776 KB Output is correct
21 Correct 154 ms 509628 KB Output is correct
22 Correct 144 ms 509776 KB Output is correct
23 Correct 155 ms 509488 KB Output is correct
24 Correct 153 ms 509672 KB Output is correct
25 Correct 149 ms 509520 KB Output is correct
26 Correct 147 ms 509776 KB Output is correct
27 Correct 183 ms 509776 KB Output is correct
28 Correct 146 ms 509776 KB Output is correct
29 Correct 146 ms 509776 KB Output is correct
30 Correct 186 ms 509776 KB Output is correct
31 Correct 156 ms 509736 KB Output is correct
32 Correct 141 ms 509660 KB Output is correct
33 Correct 146 ms 509604 KB Output is correct
34 Correct 147 ms 509520 KB Output is correct
35 Correct 152 ms 509620 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 509336 KB Output is correct
2 Correct 150 ms 509572 KB Output is correct
3 Correct 164 ms 509856 KB Output is correct
4 Correct 145 ms 509776 KB Output is correct
5 Correct 148 ms 509624 KB Output is correct
6 Correct 178 ms 509656 KB Output is correct
7 Correct 146 ms 509624 KB Output is correct
8 Correct 144 ms 509724 KB Output is correct
9 Correct 145 ms 509512 KB Output is correct
10 Correct 150 ms 509596 KB Output is correct
11 Correct 145 ms 509672 KB Output is correct
12 Correct 141 ms 509264 KB Output is correct
13 Correct 151 ms 509676 KB Output is correct
14 Correct 178 ms 509584 KB Output is correct
15 Correct 145 ms 509692 KB Output is correct
16 Correct 147 ms 509560 KB Output is correct
17 Correct 158 ms 509672 KB Output is correct
18 Correct 154 ms 509524 KB Output is correct
19 Correct 150 ms 509516 KB Output is correct
20 Correct 198 ms 509776 KB Output is correct
21 Correct 154 ms 509628 KB Output is correct
22 Correct 144 ms 509776 KB Output is correct
23 Correct 155 ms 509488 KB Output is correct
24 Correct 153 ms 509672 KB Output is correct
25 Correct 149 ms 509520 KB Output is correct
26 Correct 147 ms 509776 KB Output is correct
27 Correct 183 ms 509776 KB Output is correct
28 Correct 146 ms 509776 KB Output is correct
29 Correct 146 ms 509776 KB Output is correct
30 Correct 186 ms 509776 KB Output is correct
31 Correct 156 ms 509736 KB Output is correct
32 Correct 141 ms 509660 KB Output is correct
33 Correct 146 ms 509604 KB Output is correct
34 Correct 147 ms 509520 KB Output is correct
35 Correct 152 ms 509620 KB Output is correct
36 Correct 272 ms 520056 KB Output is correct
37 Correct 349 ms 525900 KB Output is correct
38 Correct 402 ms 525896 KB Output is correct
39 Correct 390 ms 527192 KB Output is correct
40 Correct 384 ms 526968 KB Output is correct
41 Correct 388 ms 526916 KB Output is correct
42 Correct 393 ms 526852 KB Output is correct
43 Correct 288 ms 523464 KB Output is correct
44 Correct 285 ms 523344 KB Output is correct
45 Correct 285 ms 523600 KB Output is correct
46 Correct 281 ms 523488 KB Output is correct
47 Correct 366 ms 525896 KB Output is correct
48 Correct 388 ms 526988 KB Output is correct
49 Correct 396 ms 527112 KB Output is correct
50 Correct 279 ms 523424 KB Output is correct
51 Correct 303 ms 523484 KB Output is correct
52 Correct 349 ms 525892 KB Output is correct
53 Correct 400 ms 527016 KB Output is correct
54 Correct 410 ms 526992 KB Output is correct
55 Correct 289 ms 523380 KB Output is correct
56 Correct 284 ms 523600 KB Output is correct
57 Correct 346 ms 525268 KB Output is correct
58 Correct 344 ms 525812 KB Output is correct
59 Correct 339 ms 525772 KB Output is correct
60 Correct 390 ms 526856 KB Output is correct
61 Correct 405 ms 526924 KB Output is correct
62 Correct 396 ms 526852 KB Output is correct
63 Correct 391 ms 526856 KB Output is correct
64 Correct 284 ms 523328 KB Output is correct
65 Correct 292 ms 523492 KB Output is correct
66 Correct 284 ms 523452 KB Output is correct
67 Correct 281 ms 523344 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 525640 KB Output is correct
2 Correct 1376 ms 525892 KB Output is correct
3 Correct 1293 ms 525808 KB Output is correct
4 Correct 1268 ms 526988 KB Output is correct
5 Correct 1351 ms 527068 KB Output is correct
6 Correct 1311 ms 526892 KB Output is correct
7 Correct 1342 ms 526852 KB Output is correct
8 Correct 1000 ms 523380 KB Output is correct
9 Correct 1121 ms 523344 KB Output is correct
10 Correct 1236 ms 523344 KB Output is correct
11 Correct 1244 ms 523340 KB Output is correct
12 Correct 1012 ms 523496 KB Output is correct
13 Correct 1004 ms 523408 KB Output is correct
14 Correct 146 ms 509264 KB Output is correct
15 Correct 154 ms 509768 KB Output is correct
16 Correct 148 ms 509520 KB Output is correct
17 Correct 339 ms 525816 KB Output is correct
18 Correct 383 ms 526856 KB Output is correct
19 Correct 401 ms 526936 KB Output is correct
20 Correct 280 ms 523532 KB Output is correct
21 Correct 286 ms 523320 KB Output is correct
22 Correct 340 ms 525672 KB Output is correct
23 Correct 451 ms 526860 KB Output is correct
24 Correct 377 ms 526944 KB Output is correct
25 Correct 275 ms 523344 KB Output is correct
26 Correct 279 ms 523344 KB Output is correct
27 Correct 156 ms 509772 KB Output is correct
28 Correct 149 ms 509776 KB Output is correct
29 Correct 146 ms 509776 KB Output is correct
30 Correct 147 ms 509492 KB Output is correct
31 Correct 143 ms 509664 KB Output is correct
32 Correct 167 ms 509776 KB Output is correct
33 Correct 145 ms 509772 KB Output is correct
34 Correct 151 ms 509776 KB Output is correct
35 Correct 144 ms 509520 KB Output is correct
36 Correct 138 ms 509544 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 513368 KB Output is correct
2 Correct 1124 ms 525896 KB Output is correct
3 Correct 1170 ms 525896 KB Output is correct
4 Correct 1204 ms 526856 KB Output is correct
5 Correct 1166 ms 526888 KB Output is correct
6 Correct 1224 ms 527024 KB Output is correct
7 Correct 1127 ms 526888 KB Output is correct
8 Correct 949 ms 523348 KB Output is correct
9 Correct 962 ms 523344 KB Output is correct
10 Correct 944 ms 523500 KB Output is correct
11 Correct 943 ms 523600 KB Output is correct
12 Correct 360 ms 526152 KB Output is correct
13 Correct 413 ms 527068 KB Output is correct
14 Correct 387 ms 527108 KB Output is correct
15 Correct 279 ms 523344 KB Output is correct
16 Correct 273 ms 523328 KB Output is correct
17 Correct 358 ms 525136 KB Output is correct
18 Correct 353 ms 525676 KB Output is correct
19 Correct 355 ms 525768 KB Output is correct
20 Correct 393 ms 526856 KB Output is correct
21 Correct 386 ms 527040 KB Output is correct
22 Correct 387 ms 526856 KB Output is correct
23 Correct 530 ms 526876 KB Output is correct
24 Correct 297 ms 523556 KB Output is correct
25 Correct 284 ms 523448 KB Output is correct
26 Correct 285 ms 523376 KB Output is correct
27 Correct 289 ms 523344 KB Output is correct
28 Correct 153 ms 509776 KB Output is correct
29 Correct 154 ms 509776 KB Output is correct
30 Correct 165 ms 509776 KB Output is correct
31 Correct 160 ms 509680 KB Output is correct
32 Correct 156 ms 509840 KB Output is correct
33 Correct 168 ms 509476 KB Output is correct
34 Correct 154 ms 509712 KB Output is correct
35 Correct 156 ms 509632 KB Output is correct
36 Correct 155 ms 509776 KB Output is correct
37 Correct 162 ms 509776 KB Output is correct
38 Correct 155 ms 509776 KB Output is correct
39 Correct 169 ms 509776 KB Output is correct
40 Correct 158 ms 509544 KB Output is correct
41 Correct 153 ms 509500 KB Output is correct
42 Correct 156 ms 509512 KB Output is correct
43 Correct 151 ms 509520 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 509336 KB Output is correct
2 Correct 150 ms 509572 KB Output is correct
3 Correct 164 ms 509856 KB Output is correct
4 Correct 145 ms 509776 KB Output is correct
5 Correct 148 ms 509624 KB Output is correct
6 Correct 178 ms 509656 KB Output is correct
7 Correct 146 ms 509624 KB Output is correct
8 Correct 144 ms 509724 KB Output is correct
9 Correct 145 ms 509512 KB Output is correct
10 Correct 150 ms 509596 KB Output is correct
11 Correct 145 ms 509672 KB Output is correct
12 Correct 141 ms 509264 KB Output is correct
13 Correct 151 ms 509676 KB Output is correct
14 Correct 178 ms 509584 KB Output is correct
15 Correct 145 ms 509692 KB Output is correct
16 Correct 147 ms 509560 KB Output is correct
17 Correct 158 ms 509672 KB Output is correct
18 Correct 154 ms 509524 KB Output is correct
19 Correct 150 ms 509516 KB Output is correct
20 Correct 198 ms 509776 KB Output is correct
21 Correct 154 ms 509628 KB Output is correct
22 Correct 144 ms 509776 KB Output is correct
23 Correct 155 ms 509488 KB Output is correct
24 Correct 153 ms 509672 KB Output is correct
25 Correct 149 ms 509520 KB Output is correct
26 Correct 147 ms 509776 KB Output is correct
27 Correct 183 ms 509776 KB Output is correct
28 Correct 146 ms 509776 KB Output is correct
29 Correct 146 ms 509776 KB Output is correct
30 Correct 186 ms 509776 KB Output is correct
31 Correct 156 ms 509736 KB Output is correct
32 Correct 141 ms 509660 KB Output is correct
33 Correct 146 ms 509604 KB Output is correct
34 Correct 147 ms 509520 KB Output is correct
35 Correct 152 ms 509620 KB Output is correct
36 Correct 272 ms 520056 KB Output is correct
37 Correct 349 ms 525900 KB Output is correct
38 Correct 402 ms 525896 KB Output is correct
39 Correct 390 ms 527192 KB Output is correct
40 Correct 384 ms 526968 KB Output is correct
41 Correct 388 ms 526916 KB Output is correct
42 Correct 393 ms 526852 KB Output is correct
43 Correct 288 ms 523464 KB Output is correct
44 Correct 285 ms 523344 KB Output is correct
45 Correct 285 ms 523600 KB Output is correct
46 Correct 281 ms 523488 KB Output is correct
47 Correct 366 ms 525896 KB Output is correct
48 Correct 388 ms 526988 KB Output is correct
49 Correct 396 ms 527112 KB Output is correct
50 Correct 279 ms 523424 KB Output is correct
51 Correct 303 ms 523484 KB Output is correct
52 Correct 349 ms 525892 KB Output is correct
53 Correct 400 ms 527016 KB Output is correct
54 Correct 410 ms 526992 KB Output is correct
55 Correct 289 ms 523380 KB Output is correct
56 Correct 284 ms 523600 KB Output is correct
57 Correct 346 ms 525268 KB Output is correct
58 Correct 344 ms 525812 KB Output is correct
59 Correct 339 ms 525772 KB Output is correct
60 Correct 390 ms 526856 KB Output is correct
61 Correct 405 ms 526924 KB Output is correct
62 Correct 396 ms 526852 KB Output is correct
63 Correct 391 ms 526856 KB Output is correct
64 Correct 284 ms 523328 KB Output is correct
65 Correct 292 ms 523492 KB Output is correct
66 Correct 284 ms 523452 KB Output is correct
67 Correct 281 ms 523344 KB Output is correct
68 Correct 1100 ms 525640 KB Output is correct
69 Correct 1376 ms 525892 KB Output is correct
70 Correct 1293 ms 525808 KB Output is correct
71 Correct 1268 ms 526988 KB Output is correct
72 Correct 1351 ms 527068 KB Output is correct
73 Correct 1311 ms 526892 KB Output is correct
74 Correct 1342 ms 526852 KB Output is correct
75 Correct 1000 ms 523380 KB Output is correct
76 Correct 1121 ms 523344 KB Output is correct
77 Correct 1236 ms 523344 KB Output is correct
78 Correct 1244 ms 523340 KB Output is correct
79 Correct 1012 ms 523496 KB Output is correct
80 Correct 1004 ms 523408 KB Output is correct
81 Correct 146 ms 509264 KB Output is correct
82 Correct 154 ms 509768 KB Output is correct
83 Correct 148 ms 509520 KB Output is correct
84 Correct 339 ms 525816 KB Output is correct
85 Correct 383 ms 526856 KB Output is correct
86 Correct 401 ms 526936 KB Output is correct
87 Correct 280 ms 523532 KB Output is correct
88 Correct 286 ms 523320 KB Output is correct
89 Correct 340 ms 525672 KB Output is correct
90 Correct 451 ms 526860 KB Output is correct
91 Correct 377 ms 526944 KB Output is correct
92 Correct 275 ms 523344 KB Output is correct
93 Correct 279 ms 523344 KB Output is correct
94 Correct 156 ms 509772 KB Output is correct
95 Correct 149 ms 509776 KB Output is correct
96 Correct 146 ms 509776 KB Output is correct
97 Correct 147 ms 509492 KB Output is correct
98 Correct 143 ms 509664 KB Output is correct
99 Correct 167 ms 509776 KB Output is correct
100 Correct 145 ms 509772 KB Output is correct
101 Correct 151 ms 509776 KB Output is correct
102 Correct 144 ms 509520 KB Output is correct
103 Correct 138 ms 509544 KB Output is correct
104 Correct 1265 ms 523996 KB Output is correct
105 Correct 1451 ms 525876 KB Output is correct
106 Correct 1524 ms 525796 KB Output is correct
107 Correct 1398 ms 527044 KB Output is correct
108 Incorrect 1472 ms 526856 KB 19976th lines differ - on the 1st token, expected: '2', found: '1'
109 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 517760 KB Output is correct
2 Correct 966 ms 523344 KB Output is correct
3 Correct 991 ms 523328 KB Output is correct
4 Correct 1010 ms 523400 KB Output is correct
5 Correct 977 ms 523496 KB Output is correct
6 Correct 1016 ms 523600 KB Output is correct
7 Correct 978 ms 523420 KB Output is correct
8 Correct 149 ms 509300 KB Output is correct
9 Correct 147 ms 509684 KB Output is correct
10 Correct 158 ms 509496 KB Output is correct
11 Correct 147 ms 509336 KB Output is correct
12 Correct 150 ms 509572 KB Output is correct
13 Correct 164 ms 509856 KB Output is correct
14 Correct 145 ms 509776 KB Output is correct
15 Correct 148 ms 509624 KB Output is correct
16 Correct 178 ms 509656 KB Output is correct
17 Correct 146 ms 509624 KB Output is correct
18 Correct 144 ms 509724 KB Output is correct
19 Correct 145 ms 509512 KB Output is correct
20 Correct 150 ms 509596 KB Output is correct
21 Correct 145 ms 509672 KB Output is correct
22 Correct 141 ms 509264 KB Output is correct
23 Correct 151 ms 509676 KB Output is correct
24 Correct 178 ms 509584 KB Output is correct
25 Correct 145 ms 509692 KB Output is correct
26 Correct 147 ms 509560 KB Output is correct
27 Correct 158 ms 509672 KB Output is correct
28 Correct 154 ms 509524 KB Output is correct
29 Correct 150 ms 509516 KB Output is correct
30 Correct 198 ms 509776 KB Output is correct
31 Correct 154 ms 509628 KB Output is correct
32 Correct 144 ms 509776 KB Output is correct
33 Correct 155 ms 509488 KB Output is correct
34 Correct 153 ms 509672 KB Output is correct
35 Correct 149 ms 509520 KB Output is correct
36 Correct 147 ms 509776 KB Output is correct
37 Correct 183 ms 509776 KB Output is correct
38 Correct 146 ms 509776 KB Output is correct
39 Correct 146 ms 509776 KB Output is correct
40 Correct 186 ms 509776 KB Output is correct
41 Correct 156 ms 509736 KB Output is correct
42 Correct 141 ms 509660 KB Output is correct
43 Correct 146 ms 509604 KB Output is correct
44 Correct 147 ms 509520 KB Output is correct
45 Correct 152 ms 509620 KB Output is correct
46 Correct 272 ms 520056 KB Output is correct
47 Correct 349 ms 525900 KB Output is correct
48 Correct 402 ms 525896 KB Output is correct
49 Correct 390 ms 527192 KB Output is correct
50 Correct 384 ms 526968 KB Output is correct
51 Correct 388 ms 526916 KB Output is correct
52 Correct 393 ms 526852 KB Output is correct
53 Correct 288 ms 523464 KB Output is correct
54 Correct 285 ms 523344 KB Output is correct
55 Correct 285 ms 523600 KB Output is correct
56 Correct 281 ms 523488 KB Output is correct
57 Correct 366 ms 525896 KB Output is correct
58 Correct 388 ms 526988 KB Output is correct
59 Correct 396 ms 527112 KB Output is correct
60 Correct 279 ms 523424 KB Output is correct
61 Correct 303 ms 523484 KB Output is correct
62 Correct 349 ms 525892 KB Output is correct
63 Correct 400 ms 527016 KB Output is correct
64 Correct 410 ms 526992 KB Output is correct
65 Correct 289 ms 523380 KB Output is correct
66 Correct 284 ms 523600 KB Output is correct
67 Correct 346 ms 525268 KB Output is correct
68 Correct 344 ms 525812 KB Output is correct
69 Correct 339 ms 525772 KB Output is correct
70 Correct 390 ms 526856 KB Output is correct
71 Correct 405 ms 526924 KB Output is correct
72 Correct 396 ms 526852 KB Output is correct
73 Correct 391 ms 526856 KB Output is correct
74 Correct 284 ms 523328 KB Output is correct
75 Correct 292 ms 523492 KB Output is correct
76 Correct 284 ms 523452 KB Output is correct
77 Correct 281 ms 523344 KB Output is correct
78 Correct 1100 ms 525640 KB Output is correct
79 Correct 1376 ms 525892 KB Output is correct
80 Correct 1293 ms 525808 KB Output is correct
81 Correct 1268 ms 526988 KB Output is correct
82 Correct 1351 ms 527068 KB Output is correct
83 Correct 1311 ms 526892 KB Output is correct
84 Correct 1342 ms 526852 KB Output is correct
85 Correct 1000 ms 523380 KB Output is correct
86 Correct 1121 ms 523344 KB Output is correct
87 Correct 1236 ms 523344 KB Output is correct
88 Correct 1244 ms 523340 KB Output is correct
89 Correct 1012 ms 523496 KB Output is correct
90 Correct 1004 ms 523408 KB Output is correct
91 Correct 146 ms 509264 KB Output is correct
92 Correct 154 ms 509768 KB Output is correct
93 Correct 148 ms 509520 KB Output is correct
94 Correct 339 ms 525816 KB Output is correct
95 Correct 383 ms 526856 KB Output is correct
96 Correct 401 ms 526936 KB Output is correct
97 Correct 280 ms 523532 KB Output is correct
98 Correct 286 ms 523320 KB Output is correct
99 Correct 340 ms 525672 KB Output is correct
100 Correct 451 ms 526860 KB Output is correct
101 Correct 377 ms 526944 KB Output is correct
102 Correct 275 ms 523344 KB Output is correct
103 Correct 279 ms 523344 KB Output is correct
104 Correct 156 ms 509772 KB Output is correct
105 Correct 149 ms 509776 KB Output is correct
106 Correct 146 ms 509776 KB Output is correct
107 Correct 147 ms 509492 KB Output is correct
108 Correct 143 ms 509664 KB Output is correct
109 Correct 167 ms 509776 KB Output is correct
110 Correct 145 ms 509772 KB Output is correct
111 Correct 151 ms 509776 KB Output is correct
112 Correct 144 ms 509520 KB Output is correct
113 Correct 138 ms 509544 KB Output is correct
114 Correct 434 ms 513368 KB Output is correct
115 Correct 1124 ms 525896 KB Output is correct
116 Correct 1170 ms 525896 KB Output is correct
117 Correct 1204 ms 526856 KB Output is correct
118 Correct 1166 ms 526888 KB Output is correct
119 Correct 1224 ms 527024 KB Output is correct
120 Correct 1127 ms 526888 KB Output is correct
121 Correct 949 ms 523348 KB Output is correct
122 Correct 962 ms 523344 KB Output is correct
123 Correct 944 ms 523500 KB Output is correct
124 Correct 943 ms 523600 KB Output is correct
125 Correct 360 ms 526152 KB Output is correct
126 Correct 413 ms 527068 KB Output is correct
127 Correct 387 ms 527108 KB Output is correct
128 Correct 279 ms 523344 KB Output is correct
129 Correct 273 ms 523328 KB Output is correct
130 Correct 358 ms 525136 KB Output is correct
131 Correct 353 ms 525676 KB Output is correct
132 Correct 355 ms 525768 KB Output is correct
133 Correct 393 ms 526856 KB Output is correct
134 Correct 386 ms 527040 KB Output is correct
135 Correct 387 ms 526856 KB Output is correct
136 Correct 530 ms 526876 KB Output is correct
137 Correct 297 ms 523556 KB Output is correct
138 Correct 284 ms 523448 KB Output is correct
139 Correct 285 ms 523376 KB Output is correct
140 Correct 289 ms 523344 KB Output is correct
141 Correct 153 ms 509776 KB Output is correct
142 Correct 154 ms 509776 KB Output is correct
143 Correct 165 ms 509776 KB Output is correct
144 Correct 160 ms 509680 KB Output is correct
145 Correct 156 ms 509840 KB Output is correct
146 Correct 168 ms 509476 KB Output is correct
147 Correct 154 ms 509712 KB Output is correct
148 Correct 156 ms 509632 KB Output is correct
149 Correct 155 ms 509776 KB Output is correct
150 Correct 162 ms 509776 KB Output is correct
151 Correct 155 ms 509776 KB Output is correct
152 Correct 169 ms 509776 KB Output is correct
153 Correct 158 ms 509544 KB Output is correct
154 Correct 153 ms 509500 KB Output is correct
155 Correct 156 ms 509512 KB Output is correct
156 Correct 151 ms 509520 KB Output is correct
157 Correct 1265 ms 523996 KB Output is correct
158 Correct 1451 ms 525876 KB Output is correct
159 Correct 1524 ms 525796 KB Output is correct
160 Correct 1398 ms 527044 KB Output is correct
161 Incorrect 1472 ms 526856 KB 19976th lines differ - on the 1st token, expected: '2', found: '1'
162 Halted 0 ms 0 KB -