oj.uz

Submission #752729

# Submission time Handle Problem Language Result Execution time Memory
752729 2023-06-03T13:41:42 Z Sam_a17 Food Court (JOI21_foodcourt) C++17
100 / 100
 893 ms 269160 KB 
#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 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(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}
 
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> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} 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(deque <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, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// 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};

long long ka() {
	long long x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}

// 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 != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
 
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 250005;
long long n, m, q;
vector<pair<long long, pair<long long, long long>>> to_add[N], to_del[N], qq[N];
vector<pair<long long, pair<long long, long long>>> to_add2[N], to_del2[N];
deque<pair<long long, pair<long long, long long>>> st[N];
long long cnt[N];

struct node {
  long long type;
  long long l, r, k, c;
};

vector<node> queries;

struct segTree {
 
  struct node {
    long long value, cur, lazy;
  };

  int size = 1;
  vector<node> tree;

  void init(int s) {
    while(s > size) {
      size *= 2;
    }
    tree.assign(2 * size - 1, {0, 0, 0});
  }

  void propagate(int x, int lx, int rx) {
    if(rx - lx == 1 || !tree[x].lazy) {
      return;
    }

    int mid = (lx + rx) / 2;
    tree[2 * x + 1].value += tree[x].lazy * (mid - lx);
    tree[2 * x + 1].lazy += tree[x].lazy;

    tree[2 * x + 2].value += tree[x].lazy * (rx - mid);
    tree[2 * x + 2].lazy += tree[x].lazy;

    tree[x].lazy = 0;
  }

  void upd(int l, int r, long long value, long long vul, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return;
    }

    if(lx >= l && rx <= r) {
      if(value == -1) {
        tree[x].value = 0;
        tree[x].cur = 0;
        tree[x].lazy = 0;
      } else {
        tree[x] = {value, vul, value};
        propagate(x, lx, rx);
      }
      return;
    }

    int mid = (lx + rx) / 2;
    upd(l, r, value, vul, 2 * x + 1, lx, mid);
    upd(l, r, value, vul, 2 * x + 2, mid, rx);
    tree[x].value = tree[2 * x + 1].value + tree[2 * x + 2].value;
  }

  void upd(int l, int r, long long value, long long vul) {
    upd(l, r, value, vul, 0, 0, size);
  }

  long long sum(int l, int r, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return 0;
    }

    if(lx >= l && rx <= r) {
      return tree[x].value;
    }

    int mid = (lx + rx) / 2;
    long long s1 = sum(l, r, 2 * x + 1, lx, mid);
    long long s2 = sum(l, r, 2 * x + 2, mid, rx);
    return s1 + s2;
  }

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

  pair<long long, long long> qry(long long d, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(rx - lx == 1) {
      return {tree[x].cur, lx};
    }

    int mid = (lx + rx) / 2;
    if(tree[2 * x + 1].value >= d) {
      return qry(d, 2 * x + 1, lx, mid);
    } else { 
      return qry(d - tree[2 * x + 1].value, 2 * x + 2, mid, rx);
    }
  }

  pair<long long, long long> qry(long long d) {
    if(tree[0].value < d) {
      return {0ll, 0ll};
    }

    return qry(d, 0, 0, size);
  }
};
 
segTree seg;


struct segtree {
  struct node {
  long long mn, cnt, sum, prefix, suffix, maxSubset;
  };

  node combine (node a, node b) {
    node c;
    c.mn = min(a.mn, b.mn);
    c.sum = a.sum + b.sum;
    c.prefix = max(a.sum + b.prefix, a.prefix);
    c.suffix = max(b.sum + a.suffix, b.suffix);
    c.maxSubset = max({a.maxSubset, b.maxSubset, a.suffix + b.prefix});
    return c;
  }

  vector<node> mTree;
  int size;

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

  void set(int u, ll v, int x, int lx, int rx) {
    if(rx - lx == 1) {
      mTree[x] = {v, 1, v, max(v, 0LL),max(v, 0LL),max(v, 0LL)};
      return;
    }

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

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

  node range (int l, int r, int x, int lx, int rx) {
    if(l >= rx || lx >= r) {
      return {INT32_MAX, 1, 0,0,0,0};
    }
    if(lx >= l && r >= rx) {
      return mTree[x];
    }

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

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

segtree seg_sum;

void solve_() {
  cin >> n >> m >> q;

  int oki = 1;
  for(int i = 0; i < q; i++) {
    int type; cin >> type;

    if(type == 1) {
      long long l, r, c, k; 
      cin >> l >> r >> c >> k;
      queries.push_back({type, l, r, k, c});
    } else if(type == 2) {
      long long l, r, k; cin >> l >> r >> k;
      queries.push_back({type, l, r, k, -1});
      oki = 0;
    } else {
      long long l, r; cin >> l >> r;
      queries.push_back({type, l, r, -1, -1});
    }
  }

  // if(oki) {
    seg.init(q + 1);
    seg_sum.init(q + 1);
    vector<long long> answ(q + 1), out(q + 1);
    for(int i = 0; i < q; i++) {
      int type = queries[i].type;
      if(type == 1) {
        long long l = queries[i].l;
        long long r = queries[i].r;
        long long c = queries[i].c;
        long long k = queries[i].k;

        to_add[l].push_back({i, {k, c}});
        to_del[r + 1].push_back({i, {k, c}});
      } else if(type == 3) {
        long long a = queries[i].l;
        long long b = queries[i].r;
        qq[a].push_back({i, {b, -1}});
        out[i] = 1;
      } else {
        long long l = queries[i].l;
        long long r = queries[i].r;
        long long k = queries[i].k;

        to_add2[l].push_back({i, {k, -1}});
        to_del2[r + 1].push_back({i, {k, -1}});
      }
    }

    vector<long long> sub(q + 1);
    for(int i = 1; i <= n; i++) {
      for(auto j: to_add[i]) {
        seg.upd(j.first, j.first + 1, j.second.first, j.second.second);
        seg_sum.set(j.first, j.second.first);
      }

      for(auto j: to_del[i]) {
        seg.upd(j.first, j.first + 1, -1, -1);
        seg_sum.set(j.first, 0);
      } 
      
      for(auto j: to_add2[i]) {
        seg_sum.set(j.first, -j.second.first);
      }

      for(auto j: to_del2[i]) {
        seg_sum.set(j.first, 0);
      }

      for(auto j: qq[i]) {
        long long sfe = seg_sum.range(0, j.first + 1).suffix;
        if(j.second.first > sfe) {
          answ[j.first] = 0;
          continue;
        }

        long long all = seg.sum(0, j.first + 1);
        all -= sfe;
        all += j.second.first;
        answ[j.first] = seg.qry(all).first;
      }
    }

    for(int i = 0; i < q; i++) {
      if(out[i]) {
        cout << answ[i] << '\n';
      }
    }

  // } else {
  //   long long it = 0, ok = 1;
  //   set<int> not_empty;
  //   vector<bool> have(n + 1);
  //   for(int t = 0; t < q; t++) {
  //     int type = queries[t].type;
  //     if(type == 1) {
  //       long long l, r, c, k;
  //       l = queries[t].l;
  //       r = queries[t].r;
  //       c = queries[t].c;
  //       k = queries[t].k;
  //       for(int i = l; i <= r; i++) {
  //         cnt[i] += k; 
  //         st[i].push_back({it, {c, k}});
  //         if(!have[i]) {
  //           have[i] = true;
  //           not_empty.insert(i);
  //         }
  //       }

  //       if(k != 1) ok = 0;
  //     } else if(type == 2) {
  //       long long l, r, k; 
  //       l = queries[t].l;
  //       r = queries[t].r;
  //       k = queries[t].k;
  //       if(k != 1) ok = 0;

  //       auto it = not_empty.lower_bound(l);
  //       vector<int> to_del;
  //       while(it != not_empty.end() && *it <= r) {
  //         int i = *it;
  //         if(ok) {
  //           if(!st[i].empty()) {
  //             st[i].pop_front();
  //           }  
  //         } else {
  //           long long curr = k;
  //           while(!st[i].empty()) {
  //             if(curr >= st[i].front().second.second) {
  //               curr -= st[i].front().second.second;
  //               st[i].pop_front();
  //             } else {
  //               st[i].front().second.second -= curr;
  //               break;
  //             }
  //           }
  //         }
  //         cnt[i] -= k;
  //         cnt[i] = max(cnt[i], 0ll);
  //         if(cnt[i] == 0) {
  //           to_del.push_back(i);
  //         }
  //         it = next(it);
  //       }

  //       for(auto i: to_del) {
  //         have[i] = false;
  //         not_empty.erase(i);
  //       }

  //     } else {
  //       long long a, b; 
  //       // cin >> a >> b;
  //       a = queries[t].l;
  //       b = queries[t].r;

  //       if(cnt[a] < b) {
  //         cout << 0 << '\n';
  //       } else {
  //         if(ok) {
  //           cout << st[a][b - 1].second.first << '\n';
  //         } else {
  //           for(int i = 0; i < sz(st[a]); i++) {
  //             if(b > st[a][i].second.second) {
  //               b -= st[a][i].second.second;
  //             } else {
  //               cout << st[a][i].second.first << '\n';
  //               break;
  //             }
  //           }
  //         }
  //       }
  //     }
  //     it++;
  //   }
  // }
}
 
int main() {
  setIO();
  
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1; 
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

foodcourt.cpp: In function 'void solve_()':
foodcourt.cpp:283:7: warning: variable 'oki' set but not used [-Wunused-but-set-variable]
  283 |   int oki = 1;
      |       ^~~
foodcourt.cpp: In function 'void setIO(std::string)':
foodcourt.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 194476 KB Output is correct
2 Correct 114 ms 194516 KB Output is correct
3 Correct 127 ms 194420 KB Output is correct
4 Correct 136 ms 194548 KB Output is correct
5 Correct 130 ms 194588 KB Output is correct
6 Correct 130 ms 194540 KB Output is correct
7 Correct 126 ms 194612 KB Output is correct
8 Correct 125 ms 194564 KB Output is correct
9 Correct 120 ms 194560 KB Output is correct
10 Correct 118 ms 194508 KB Output is correct
11 Correct 127 ms 194592 KB Output is correct
12 Correct 155 ms 194604 KB Output is correct
13 Correct 145 ms 194508 KB Output is correct
14 Correct 145 ms 194552 KB Output is correct
15 Correct 138 ms 194548 KB Output is correct
16 Correct 133 ms 194600 KB Output is correct
17 Correct 137 ms 194480 KB Output is correct
18 Correct 134 ms 194532 KB Output is correct
19 Correct 130 ms 194608 KB Output is correct
20 Correct 136 ms 194720 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 194476 KB Output is correct
2 Correct 114 ms 194516 KB Output is correct
3 Correct 127 ms 194420 KB Output is correct
4 Correct 136 ms 194548 KB Output is correct
5 Correct 130 ms 194588 KB Output is correct
6 Correct 130 ms 194540 KB Output is correct
7 Correct 126 ms 194612 KB Output is correct
8 Correct 125 ms 194564 KB Output is correct
9 Correct 120 ms 194560 KB Output is correct
10 Correct 118 ms 194508 KB Output is correct
11 Correct 127 ms 194592 KB Output is correct
12 Correct 155 ms 194604 KB Output is correct
13 Correct 145 ms 194508 KB Output is correct
14 Correct 145 ms 194552 KB Output is correct
15 Correct 138 ms 194548 KB Output is correct
16 Correct 133 ms 194600 KB Output is correct
17 Correct 137 ms 194480 KB Output is correct
18 Correct 134 ms 194532 KB Output is correct
19 Correct 130 ms 194608 KB Output is correct
20 Correct 136 ms 194720 KB Output is correct
21 Correct 148 ms 194612 KB Output is correct
22 Correct 128 ms 194596 KB Output is correct
23 Correct 138 ms 194528 KB Output is correct
24 Correct 130 ms 194640 KB Output is correct
25 Correct 134 ms 194560 KB Output is correct
26 Correct 135 ms 194568 KB Output is correct
27 Correct 129 ms 194604 KB Output is correct
28 Correct 119 ms 194540 KB Output is correct
29 Correct 126 ms 194528 KB Output is correct
30 Correct 130 ms 194608 KB Output is correct
31 Correct 134 ms 194564 KB Output is correct
32 Correct 138 ms 194588 KB Output is correct
33 Correct 151 ms 194600 KB Output is correct
34 Correct 132 ms 194652 KB Output is correct
35 Correct 142 ms 194636 KB Output is correct
36 Correct 177 ms 194584 KB Output is correct
37 Correct 134 ms 194448 KB Output is correct
38 Correct 137 ms 194548 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 210792 KB Output is correct
2 Correct 253 ms 212220 KB Output is correct
3 Correct 260 ms 211988 KB Output is correct
4 Correct 219 ms 211976 KB Output is correct
5 Correct 296 ms 212204 KB Output is correct
6 Correct 237 ms 212332 KB Output is correct
7 Correct 173 ms 211336 KB Output is correct
8 Correct 203 ms 211260 KB Output is correct
9 Correct 250 ms 212276 KB Output is correct
10 Correct 228 ms 212224 KB Output is correct
11 Correct 238 ms 212248 KB Output is correct
12 Correct 243 ms 212232 KB Output is correct
13 Correct 297 ms 211052 KB Output is correct
14 Correct 235 ms 211980 KB Output is correct
15 Correct 249 ms 212440 KB Output is correct
16 Correct 277 ms 212452 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 257588 KB Output is correct
2 Correct 563 ms 256444 KB Output is correct
3 Correct 711 ms 265848 KB Output is correct
4 Correct 595 ms 256740 KB Output is correct
5 Correct 568 ms 257416 KB Output is correct
6 Correct 770 ms 266912 KB Output is correct
7 Correct 335 ms 264984 KB Output is correct
8 Correct 345 ms 264748 KB Output is correct
9 Correct 715 ms 264920 KB Output is correct
10 Correct 742 ms 264936 KB Output is correct
11 Correct 705 ms 266796 KB Output is correct
12 Correct 673 ms 266712 KB Output is correct
13 Correct 742 ms 266788 KB Output is correct
14 Correct 672 ms 266784 KB Output is correct
15 Correct 778 ms 266728 KB Output is correct
16 Correct 766 ms 266628 KB Output is correct
17 Correct 782 ms 266616 KB Output is correct
18 Correct 784 ms 266856 KB Output is correct
19 Correct 734 ms 266684 KB Output is correct
20 Correct 726 ms 266648 KB Output is correct
21 Correct 745 ms 266624 KB Output is correct
22 Correct 724 ms 266600 KB Output is correct
23 Correct 735 ms 266616 KB Output is correct
24 Correct 893 ms 266648 KB Output is correct
25 Correct 640 ms 267788 KB Output is correct
26 Correct 642 ms 268544 KB Output is correct
27 Correct 576 ms 266912 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 194476 KB Output is correct
2 Correct 114 ms 194516 KB Output is correct
3 Correct 127 ms 194420 KB Output is correct
4 Correct 136 ms 194548 KB Output is correct
5 Correct 130 ms 194588 KB Output is correct
6 Correct 130 ms 194540 KB Output is correct
7 Correct 126 ms 194612 KB Output is correct
8 Correct 125 ms 194564 KB Output is correct
9 Correct 120 ms 194560 KB Output is correct
10 Correct 118 ms 194508 KB Output is correct
11 Correct 127 ms 194592 KB Output is correct
12 Correct 155 ms 194604 KB Output is correct
13 Correct 145 ms 194508 KB Output is correct
14 Correct 145 ms 194552 KB Output is correct
15 Correct 138 ms 194548 KB Output is correct
16 Correct 133 ms 194600 KB Output is correct
17 Correct 137 ms 194480 KB Output is correct
18 Correct 134 ms 194532 KB Output is correct
19 Correct 130 ms 194608 KB Output is correct
20 Correct 136 ms 194720 KB Output is correct
21 Correct 228 ms 210792 KB Output is correct
22 Correct 253 ms 212220 KB Output is correct
23 Correct 260 ms 211988 KB Output is correct
24 Correct 219 ms 211976 KB Output is correct
25 Correct 296 ms 212204 KB Output is correct
26 Correct 237 ms 212332 KB Output is correct
27 Correct 173 ms 211336 KB Output is correct
28 Correct 203 ms 211260 KB Output is correct
29 Correct 250 ms 212276 KB Output is correct
30 Correct 228 ms 212224 KB Output is correct
31 Correct 238 ms 212248 KB Output is correct
32 Correct 243 ms 212232 KB Output is correct
33 Correct 297 ms 211052 KB Output is correct
34 Correct 235 ms 211980 KB Output is correct
35 Correct 249 ms 212440 KB Output is correct
36 Correct 277 ms 212452 KB Output is correct
37 Correct 221 ms 210964 KB Output is correct
38 Correct 239 ms 210280 KB Output is correct
39 Correct 173 ms 210548 KB Output is correct
40 Correct 193 ms 211312 KB Output is correct
41 Correct 241 ms 212096 KB Output is correct
42 Correct 263 ms 212096 KB Output is correct
43 Correct 239 ms 212068 KB Output is correct
44 Correct 247 ms 212280 KB Output is correct
45 Correct 261 ms 212084 KB Output is correct
46 Correct 236 ms 212120 KB Output is correct
47 Correct 193 ms 211516 KB Output is correct
48 Correct 222 ms 212576 KB Output is correct
49 Correct 253 ms 209592 KB Output is correct
50 Correct 214 ms 210856 KB Output is correct
51 Correct 241 ms 212156 KB Output is correct
52 Correct 248 ms 212156 KB Output is correct
53 Correct 244 ms 210512 KB Output is correct
54 Correct 254 ms 212640 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 209848 KB Output is correct
2 Correct 243 ms 210652 KB Output is correct
3 Correct 250 ms 210640 KB Output is correct
4 Correct 199 ms 208364 KB Output is correct
5 Correct 222 ms 209532 KB Output is correct
6 Correct 242 ms 210620 KB Output is correct
7 Correct 190 ms 209436 KB Output is correct
8 Correct 190 ms 209608 KB Output is correct
9 Correct 216 ms 210104 KB Output is correct
10 Correct 210 ms 208720 KB Output is correct
11 Correct 241 ms 210616 KB Output is correct
12 Correct 243 ms 210648 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 194476 KB Output is correct
2 Correct 114 ms 194516 KB Output is correct
3 Correct 127 ms 194420 KB Output is correct
4 Correct 136 ms 194548 KB Output is correct
5 Correct 130 ms 194588 KB Output is correct
6 Correct 130 ms 194540 KB Output is correct
7 Correct 126 ms 194612 KB Output is correct
8 Correct 125 ms 194564 KB Output is correct
9 Correct 120 ms 194560 KB Output is correct
10 Correct 118 ms 194508 KB Output is correct
11 Correct 127 ms 194592 KB Output is correct
12 Correct 155 ms 194604 KB Output is correct
13 Correct 145 ms 194508 KB Output is correct
14 Correct 145 ms 194552 KB Output is correct
15 Correct 138 ms 194548 KB Output is correct
16 Correct 133 ms 194600 KB Output is correct
17 Correct 137 ms 194480 KB Output is correct
18 Correct 134 ms 194532 KB Output is correct
19 Correct 130 ms 194608 KB Output is correct
20 Correct 136 ms 194720 KB Output is correct
21 Correct 148 ms 194612 KB Output is correct
22 Correct 128 ms 194596 KB Output is correct
23 Correct 138 ms 194528 KB Output is correct
24 Correct 130 ms 194640 KB Output is correct
25 Correct 134 ms 194560 KB Output is correct
26 Correct 135 ms 194568 KB Output is correct
27 Correct 129 ms 194604 KB Output is correct
28 Correct 119 ms 194540 KB Output is correct
29 Correct 126 ms 194528 KB Output is correct
30 Correct 130 ms 194608 KB Output is correct
31 Correct 134 ms 194564 KB Output is correct
32 Correct 138 ms 194588 KB Output is correct
33 Correct 151 ms 194600 KB Output is correct
34 Correct 132 ms 194652 KB Output is correct
35 Correct 142 ms 194636 KB Output is correct
36 Correct 177 ms 194584 KB Output is correct
37 Correct 134 ms 194448 KB Output is correct
38 Correct 137 ms 194548 KB Output is correct
39 Correct 228 ms 210792 KB Output is correct
40 Correct 253 ms 212220 KB Output is correct
41 Correct 260 ms 211988 KB Output is correct
42 Correct 219 ms 211976 KB Output is correct
43 Correct 296 ms 212204 KB Output is correct
44 Correct 237 ms 212332 KB Output is correct
45 Correct 173 ms 211336 KB Output is correct
46 Correct 203 ms 211260 KB Output is correct
47 Correct 250 ms 212276 KB Output is correct
48 Correct 228 ms 212224 KB Output is correct
49 Correct 238 ms 212248 KB Output is correct
50 Correct 243 ms 212232 KB Output is correct
51 Correct 297 ms 211052 KB Output is correct
52 Correct 235 ms 211980 KB Output is correct
53 Correct 249 ms 212440 KB Output is correct
54 Correct 277 ms 212452 KB Output is correct
55 Correct 221 ms 210964 KB Output is correct
56 Correct 239 ms 210280 KB Output is correct
57 Correct 173 ms 210548 KB Output is correct
58 Correct 193 ms 211312 KB Output is correct
59 Correct 241 ms 212096 KB Output is correct
60 Correct 263 ms 212096 KB Output is correct
61 Correct 239 ms 212068 KB Output is correct
62 Correct 247 ms 212280 KB Output is correct
63 Correct 261 ms 212084 KB Output is correct
64 Correct 236 ms 212120 KB Output is correct
65 Correct 193 ms 211516 KB Output is correct
66 Correct 222 ms 212576 KB Output is correct
67 Correct 253 ms 209592 KB Output is correct
68 Correct 214 ms 210856 KB Output is correct
69 Correct 241 ms 212156 KB Output is correct
70 Correct 248 ms 212156 KB Output is correct
71 Correct 244 ms 210512 KB Output is correct
72 Correct 254 ms 212640 KB Output is correct
73 Correct 251 ms 209848 KB Output is correct
74 Correct 243 ms 210652 KB Output is correct
75 Correct 250 ms 210640 KB Output is correct
76 Correct 199 ms 208364 KB Output is correct
77 Correct 222 ms 209532 KB Output is correct
78 Correct 242 ms 210620 KB Output is correct
79 Correct 190 ms 209436 KB Output is correct
80 Correct 190 ms 209608 KB Output is correct
81 Correct 216 ms 210104 KB Output is correct
82 Correct 210 ms 208720 KB Output is correct
83 Correct 241 ms 210616 KB Output is correct
84 Correct 243 ms 210648 KB Output is correct
85 Correct 249 ms 211540 KB Output is correct
86 Correct 254 ms 212392 KB Output is correct
87 Correct 258 ms 211488 KB Output is correct
88 Correct 285 ms 212664 KB Output is correct
89 Correct 204 ms 209616 KB Output is correct
90 Correct 255 ms 212620 KB Output is correct
91 Correct 245 ms 210980 KB Output is correct
92 Correct 218 ms 210560 KB Output is correct
93 Correct 263 ms 212560 KB Output is correct
94 Correct 251 ms 212588 KB Output is correct
95 Correct 234 ms 212408 KB Output is correct
96 Correct 239 ms 212632 KB Output is correct
97 Correct 301 ms 212616 KB Output is correct
98 Correct 215 ms 211308 KB Output is correct
99 Correct 195 ms 212252 KB Output is correct
100 Correct 211 ms 211360 KB Output is correct
101 Correct 274 ms 213164 KB Output is correct
102 Correct 264 ms 212760 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 194476 KB Output is correct
2 Correct 114 ms 194516 KB Output is correct
3 Correct 127 ms 194420 KB Output is correct
4 Correct 136 ms 194548 KB Output is correct
5 Correct 130 ms 194588 KB Output is correct
6 Correct 130 ms 194540 KB Output is correct
7 Correct 126 ms 194612 KB Output is correct
8 Correct 125 ms 194564 KB Output is correct
9 Correct 120 ms 194560 KB Output is correct
10 Correct 118 ms 194508 KB Output is correct
11 Correct 127 ms 194592 KB Output is correct
12 Correct 155 ms 194604 KB Output is correct
13 Correct 145 ms 194508 KB Output is correct
14 Correct 145 ms 194552 KB Output is correct
15 Correct 138 ms 194548 KB Output is correct
16 Correct 133 ms 194600 KB Output is correct
17 Correct 137 ms 194480 KB Output is correct
18 Correct 134 ms 194532 KB Output is correct
19 Correct 130 ms 194608 KB Output is correct
20 Correct 136 ms 194720 KB Output is correct
21 Correct 148 ms 194612 KB Output is correct
22 Correct 128 ms 194596 KB Output is correct
23 Correct 138 ms 194528 KB Output is correct
24 Correct 130 ms 194640 KB Output is correct
25 Correct 134 ms 194560 KB Output is correct
26 Correct 135 ms 194568 KB Output is correct
27 Correct 129 ms 194604 KB Output is correct
28 Correct 119 ms 194540 KB Output is correct
29 Correct 126 ms 194528 KB Output is correct
30 Correct 130 ms 194608 KB Output is correct
31 Correct 134 ms 194564 KB Output is correct
32 Correct 138 ms 194588 KB Output is correct
33 Correct 151 ms 194600 KB Output is correct
34 Correct 132 ms 194652 KB Output is correct
35 Correct 142 ms 194636 KB Output is correct
36 Correct 177 ms 194584 KB Output is correct
37 Correct 134 ms 194448 KB Output is correct
38 Correct 137 ms 194548 KB Output is correct
39 Correct 228 ms 210792 KB Output is correct
40 Correct 253 ms 212220 KB Output is correct
41 Correct 260 ms 211988 KB Output is correct
42 Correct 219 ms 211976 KB Output is correct
43 Correct 296 ms 212204 KB Output is correct
44 Correct 237 ms 212332 KB Output is correct
45 Correct 173 ms 211336 KB Output is correct
46 Correct 203 ms 211260 KB Output is correct
47 Correct 250 ms 212276 KB Output is correct
48 Correct 228 ms 212224 KB Output is correct
49 Correct 238 ms 212248 KB Output is correct
50 Correct 243 ms 212232 KB Output is correct
51 Correct 297 ms 211052 KB Output is correct
52 Correct 235 ms 211980 KB Output is correct
53 Correct 249 ms 212440 KB Output is correct
54 Correct 277 ms 212452 KB Output is correct
55 Correct 737 ms 257588 KB Output is correct
56 Correct 563 ms 256444 KB Output is correct
57 Correct 711 ms 265848 KB Output is correct
58 Correct 595 ms 256740 KB Output is correct
59 Correct 568 ms 257416 KB Output is correct
60 Correct 770 ms 266912 KB Output is correct
61 Correct 335 ms 264984 KB Output is correct
62 Correct 345 ms 264748 KB Output is correct
63 Correct 715 ms 264920 KB Output is correct
64 Correct 742 ms 264936 KB Output is correct
65 Correct 705 ms 266796 KB Output is correct
66 Correct 673 ms 266712 KB Output is correct
67 Correct 742 ms 266788 KB Output is correct
68 Correct 672 ms 266784 KB Output is correct
69 Correct 778 ms 266728 KB Output is correct
70 Correct 766 ms 266628 KB Output is correct
71 Correct 782 ms 266616 KB Output is correct
72 Correct 784 ms 266856 KB Output is correct
73 Correct 734 ms 266684 KB Output is correct
74 Correct 726 ms 266648 KB Output is correct
75 Correct 745 ms 266624 KB Output is correct
76 Correct 724 ms 266600 KB Output is correct
77 Correct 735 ms 266616 KB Output is correct
78 Correct 893 ms 266648 KB Output is correct
79 Correct 640 ms 267788 KB Output is correct
80 Correct 642 ms 268544 KB Output is correct
81 Correct 576 ms 266912 KB Output is correct
82 Correct 221 ms 210964 KB Output is correct
83 Correct 239 ms 210280 KB Output is correct
84 Correct 173 ms 210548 KB Output is correct
85 Correct 193 ms 211312 KB Output is correct
86 Correct 241 ms 212096 KB Output is correct
87 Correct 263 ms 212096 KB Output is correct
88 Correct 239 ms 212068 KB Output is correct
89 Correct 247 ms 212280 KB Output is correct
90 Correct 261 ms 212084 KB Output is correct
91 Correct 236 ms 212120 KB Output is correct
92 Correct 193 ms 211516 KB Output is correct
93 Correct 222 ms 212576 KB Output is correct
94 Correct 253 ms 209592 KB Output is correct
95 Correct 214 ms 210856 KB Output is correct
96 Correct 241 ms 212156 KB Output is correct
97 Correct 248 ms 212156 KB Output is correct
98 Correct 244 ms 210512 KB Output is correct
99 Correct 254 ms 212640 KB Output is correct
100 Correct 251 ms 209848 KB Output is correct
101 Correct 243 ms 210652 KB Output is correct
102 Correct 250 ms 210640 KB Output is correct
103 Correct 199 ms 208364 KB Output is correct
104 Correct 222 ms 209532 KB Output is correct
105 Correct 242 ms 210620 KB Output is correct
106 Correct 190 ms 209436 KB Output is correct
107 Correct 190 ms 209608 KB Output is correct
108 Correct 216 ms 210104 KB Output is correct
109 Correct 210 ms 208720 KB Output is correct
110 Correct 241 ms 210616 KB Output is correct
111 Correct 243 ms 210648 KB Output is correct
112 Correct 249 ms 211540 KB Output is correct
113 Correct 254 ms 212392 KB Output is correct
114 Correct 258 ms 211488 KB Output is correct
115 Correct 285 ms 212664 KB Output is correct
116 Correct 204 ms 209616 KB Output is correct
117 Correct 255 ms 212620 KB Output is correct
118 Correct 245 ms 210980 KB Output is correct
119 Correct 218 ms 210560 KB Output is correct
120 Correct 263 ms 212560 KB Output is correct
121 Correct 251 ms 212588 KB Output is correct
122 Correct 234 ms 212408 KB Output is correct
123 Correct 239 ms 212632 KB Output is correct
124 Correct 301 ms 212616 KB Output is correct
125 Correct 215 ms 211308 KB Output is correct
126 Correct 195 ms 212252 KB Output is correct
127 Correct 211 ms 211360 KB Output is correct
128 Correct 274 ms 213164 KB Output is correct
129 Correct 264 ms 212760 KB Output is correct
130 Correct 709 ms 266500 KB Output is correct
131 Correct 539 ms 256748 KB Output is correct
132 Correct 696 ms 266484 KB Output is correct
133 Correct 729 ms 265948 KB Output is correct
134 Correct 625 ms 262056 KB Output is correct
135 Correct 764 ms 267632 KB Output is correct
136 Correct 720 ms 265940 KB Output is correct
137 Correct 745 ms 265856 KB Output is correct
138 Correct 725 ms 267412 KB Output is correct
139 Correct 727 ms 267384 KB Output is correct
140 Correct 713 ms 267412 KB Output is correct
141 Correct 740 ms 267476 KB Output is correct
142 Correct 722 ms 267392 KB Output is correct
143 Correct 888 ms 267312 KB Output is correct
144 Correct 693 ms 267436 KB Output is correct
145 Correct 787 ms 267336 KB Output is correct
146 Correct 760 ms 267296 KB Output is correct
147 Correct 798 ms 267272 KB Output is correct
148 Correct 750 ms 267328 KB Output is correct
149 Correct 732 ms 267312 KB Output is correct
150 Correct 423 ms 267440 KB Output is correct
151 Correct 625 ms 269160 KB Output is correct
152 Correct 625 ms 269080 KB Output is correct
153 Correct 633 ms 267804 KB Output is correct