oj.uz

Submission #1082505

# Submission time Handle Problem Language Result Execution time Memory
1082505 2024-08-31T14:05:02 Z vjudge1 Food Court (JOI21_foodcourt) C++17
100 / 100
 630 ms 79344 KB 
#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); i++)
#define Fore(i, a, b) for (auto i = (a); i >= (b); i--)
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ret(s) return void(cout << s);
 
const int mod = 1e9 + 7, mod2 = 998244353;
const double PI = acos(-1), eps = 1e-9;
const ull npos = string::npos;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;
 
ll add(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a+=b;return a >= m ? a - m: a;}
ll sub(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a-=b;return a < 0 ? a + m: a;}
ll mul(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;return a*b % m;}
ll bin_mul(ll a, ll b, ll m) {if (a >= m) a%=m;if (b >= m) b%=m;ll x = 0;while (b) {if (b & 1) x = (x + a) % m;a = (a + a) % m;b>>=1;}return x;}
ll bin_pow(ll a, ll b, ll m) {ll x = 1;if (a >= m) a%=m; while (b) {if (b & 1) x = bin_mul(x, a, m);a = bin_mul(a, a, m);b>>=1;}return x;}
ll power(ll a, ll b, int m) {ll x = 1;if (a >= m) a%=m; while (b) {if (b & 1) x = x*a % m;a = a*a % m;b>>=1;}return x;}
ll power(ll a, ll b) {ll x = 1;while (b) {if (b & 1) x = x*a;a = a*a;b>>=1;}return x;}
ll ceil(ll a, ll b) {return (a + b - 1)/b;}
ll to_int(const string &s) {ll x = 0; for (int i = (s[0] == '-'); i < sz(s); i++) x = x*10 + s[i] - '0';return x*(s[0] == '-' ? -1: 1);}
bool is_prime(ll n) {if (n < 2) return 0;if (n < 4) return 1;if (n % 2 == 0 || n % 3 == 0) return 0;for (ll i = 5; i*i <= n; i+=6) {if(n % i == 0 || n % (i + 2) == 0) return 0;}return 1;}
bool is_square(ll n) {ll k = sqrt(n); return k*k == n;}
ll factorial(int n) {ll x = 1;for (int i = 2; i <= n; i++) x*=i;return x;}
ll factorial(int n, int m) {ll x = 1;for (ll i = 2; i <= n; i++) x = x*i % m;return x;}
bool is_power(ll n, ll k) {while (n % k == 0) n/=k;return n == 1ll;}
string str(ll n) {if (n == 0) return "0"; string s = ""; bool c = 0; if (n < 0) c = 1, n = -n; while (n) {s+=n % 10 + '0'; n/=10;} if (c) s+='-'; Reverse(s); return s;}
string repeat(const string &s, int n) {if (n < 0) return ""; string x = ""; while (n--) x+=s; return x;}
string bin(ll n) {string s = ""; while (n) {s+=(n & 1) + '0'; n>>=1;} Reverse(s); return s;}
void sieve(vector<bool> &a) {int n = a.size(); a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(bool a[], int n) {a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(vector<int> &a) {int n = a.size(); for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
void sieve(int a[], int n) {for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
vector<pii> factorize(int n) {vector<pii> a; for (int i = 2; i*i <= n; i++) {if (n % i == 0) {int k = 0; while (n % i == 0) k++, n/=i; a.emplace_back(i, k);}} if (n > 1) a.emplace_back(n, 1); return a;}
int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(mt);}
int Log2(int n) {return 31 - __builtin_clz(n);}
template<class T> void compress(vector<T> &a) {vector<T> b; for (T &i: a) b.push_back(i); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (T &i: a) i = lower_bound(all(b), i) - b.begin() + 1;}
 
template<class A, class B> istream& operator>>(istream& in, pair<A, B> &p) {in >> p.first >> p.second; return in;}
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &p) {out << p.first << ' ' << p.second; return out;}
template<class T> istream& operator>>(istream& in, vector<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i: a) out << i << ' '; return out;}
template<class T> istream& operator>>(istream& in, vector<vector<T>> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<vector<T>> &a) {for (auto &i: a) out << i << '\n'; return out;}
template<class T> istream& operator>>(istream& in, deque<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const deque<T> &a) {for (auto &i: a) out << i << ' '; return out;}
// istream& operator>>(istream& in, __int128_t &a) {string s; in >> s; a = 0; for (auto &i: s) a = a*10 + (i - '0'); return in;}
// ostream& operator<<(ostream& out, __int128_t a) {string s = ""; while (a > 0) {s+=(int)(a % 10) + '0'; a/=10;} Reverse(s); out << s; return out;}
 
using ii = pair<ll, int>;
struct segtree_lazy_min_recursive {
    int n;
    vector<ii> t;
    vll z;
    segtree_lazy_min_recursive(int n): n(n) {
        t.resize(4*n + 5);
        z.resize(4*n + 5);
    }
    void build(const vll &a, int x, int lx, int rx) {
        if (lx == rx) {
            t[x] = {a[lx], lx};
            return;
        }
        int m = (lx + rx) >> 1;
        build(a, x << 1, lx, m);
        build(a, x << 1|1, m + 1, rx);
        t[x] = min(t[x << 1], t[x << 1|1]);
    }
    void down(int i) {
        t[i << 1].first+=z[i], t[i << 1|1].first+=z[i];
        z[i << 1]+=z[i], z[i << 1|1]+=z[i];
        z[i] = 0;
    }
    void set(int l, int r, int x, int lx, int rx, ll d) {
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r) {t[x].first+=d; z[x]+=d; return;}
        down(x);
        int m = (lx + rx) >> 1;
        set(l, r, x << 1, lx, m, d);
        set(l, r, x << 1|1, m + 1, rx, d);
        t[x] = min(t[x << 1], t[x << 1|1]);
    }
    ii get(int l, int r, int x, int lx, int rx) {
        if (lx > r || rx < l) return {1e18, 0};
        if (lx >= l && rx <= r) return t[x];
        down(x);
        int m = (lx + rx) >> 1;
        return min(get(l, r, x << 1, lx, m), get(l, r, x << 1|1, m + 1, rx));
    }
    void build(const vll &a) {build(a, 1, 0, n);}
    void set(int l, int r, ll d) {set(l, r, 1, 0, n, d);}
    ii get(int l, int r) {return get(l, r, 1, 0, n);}
};
struct segtree_lazy_sum_recursive {
    int n;
    vector<ll> t, z;
    ll merge(ll a, ll b) {return a + b;}
    segtree_lazy_sum_recursive(int n): n(n) {
        t.resize(4*n + 5);
        z.resize(4*n + 5);
    }
    void build(const vector<ll> &a, int x, int lx, int rx) {
        if (lx == rx) {
            t[x] = a[lx];
            return;
        }
        int m = (lx + rx) >> 1;
        build(a, x << 1, lx, m);
        build(a, x << 1|1, m + 1, rx);
        t[x] = merge(t[x << 1], t[x << 1|1]);
    }
    void down(int i, int l, int r) {
        ll k = z[i];
        int m = (l + r) >> 1;
        if (k != 0) {
            t[i << 1]+=k*(m - l + 1);
            t[i << 1|1]+=k*(r - m);
            z[i << 1]+=k; z[i << 1|1]+=k;
            z[i] = 0;
        }
    }
    void set(int l, int r, int x, int lx, int rx, ll d) {
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r) {t[x]+=d*(rx - lx + 1); z[x]+=d; return;}
        down(x, lx, rx);
        int m = (lx + rx) >> 1;
        set(l, r, x << 1, lx, m, d);
        set(l, r, x << 1|1, m + 1, rx, d);
        t[x] = merge(t[x << 1], t[x << 1|1]);
    }
    ll get(int l, int r, int x, int lx, int rx) {
        if (lx > r || rx < l) return 0;
        if (lx >= l && rx <= r) return t[x];
        down(x, lx, rx);
        int m = (lx + rx) >> 1;
        return merge(get(l, r, x << 1, lx, m), get(l, r, x << 1|1, m + 1, rx));
    }
    void build(const vector<ll> &a) {build(a, 1, 0, n);}
    void set(int l, int r, ll d) {set(l, r, 1, 0, n, d);}
    ll get(int l, int r) {return get(l, r, 1, 0, n);}
    int walk(int i, ll d) {
        int l = i, r = n;
        while (l < r) {
            int m = (l + r) >> 1;
            if (get(m, m) >= d) r = m;
            else l = m + 1;
        }
        return l;
    }
};
const int N = 250005;
struct que {
    int o, i, k;
    que(int o = 0, int i = 0, int k = 0): o(o), i(i), k(k) {}
};
int g[N], f[N];
vector<que> w[N];
vector<ii> a[N];
bool p[N];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cout << fixed << setprecision(10);
    int n, m, q; cin >> n >> m >> q;
    segtree_lazy_min_recursive t(q);
    segtree_lazy_sum_recursive t1(q), t2(q);
    t.build(vll(q + 1));
    FOR(i,1,q){
        int o; cin >> o;
        if (o == 1) {
            int l, r, c, k; cin >> l >> r >> c >> k;
            g[i] = c;
            w[l].eb(o, i, k); w[r + 1].eb(o, i, -k);
        } else if (o == 2) {
            int l, r, k; cin >> l >> r >> k;
            w[l].eb(o, i, -k); w[r + 1].eb(o, i, k);
        } else {
            int j; ll v; cin >> j >> v;
            p[i] = 1;
            a[j].eb(v, i);
        }
    }
    FOR(i,1,n){
        for (auto [o, j, k]: w[i]) {
            t.set(j, q, k);
            if (o == 1) t1.set(j, q, k);
            else t2.set(j, q, -k);
        }
        for (auto [v, j]: a[i]) {
            auto [u, l] = t.get(0, j);
            if (t.get(j, j).first < u + v) continue;
            v+=t2.get(j, j) + u;
            f[j] = g[t1.walk(l + 1, v)];
        }
    }
    FOR(i,1,q){
        if (p[i]) cout << f[i] << '\n';
    }
    cerr << "\nProcess returned 0 (0x0)   execution time :  " << 0.001*clock() << " s";
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 5 ms 13144 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 13148 KB Output is correct
8 Correct 7 ms 13148 KB Output is correct
9 Correct 6 ms 13148 KB Output is correct
10 Correct 6 ms 13148 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Correct 5 ms 13328 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13148 KB Output is correct
17 Correct 5 ms 13148 KB Output is correct
18 Correct 6 ms 13148 KB Output is correct
19 Correct 6 ms 13148 KB Output is correct
20 Correct 6 ms 13148 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 5 ms 13144 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 13148 KB Output is correct
8 Correct 7 ms 13148 KB Output is correct
9 Correct 6 ms 13148 KB Output is correct
10 Correct 6 ms 13148 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Correct 5 ms 13328 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13148 KB Output is correct
17 Correct 5 ms 13148 KB Output is correct
18 Correct 6 ms 13148 KB Output is correct
19 Correct 6 ms 13148 KB Output is correct
20 Correct 6 ms 13148 KB Output is correct
21 Correct 6 ms 13148 KB Output is correct
22 Correct 6 ms 13144 KB Output is correct
23 Correct 5 ms 13148 KB Output is correct
24 Correct 8 ms 13144 KB Output is correct
25 Correct 5 ms 13148 KB Output is correct
26 Correct 5 ms 13148 KB Output is correct
27 Correct 6 ms 13256 KB Output is correct
28 Correct 6 ms 13148 KB Output is correct
29 Correct 6 ms 13148 KB Output is correct
30 Correct 5 ms 13148 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 5 ms 13400 KB Output is correct
33 Correct 5 ms 13148 KB Output is correct
34 Correct 5 ms 13280 KB Output is correct
35 Correct 5 ms 13148 KB Output is correct
36 Correct 5 ms 13336 KB Output is correct
37 Correct 6 ms 13144 KB Output is correct
38 Correct 6 ms 13148 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 29788 KB Output is correct
2 Correct 73 ms 29780 KB Output is correct
3 Correct 91 ms 29756 KB Output is correct
4 Correct 68 ms 29808 KB Output is correct
5 Correct 76 ms 29788 KB Output is correct
6 Correct 81 ms 29788 KB Output is correct
7 Correct 43 ms 28540 KB Output is correct
8 Correct 48 ms 29292 KB Output is correct
9 Correct 77 ms 29784 KB Output is correct
10 Correct 79 ms 29788 KB Output is correct
11 Correct 73 ms 29792 KB Output is correct
12 Correct 69 ms 29788 KB Output is correct
13 Correct 73 ms 28036 KB Output is correct
14 Correct 81 ms 29780 KB Output is correct
15 Correct 78 ms 29656 KB Output is correct
16 Correct 73 ms 29784 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 73308 KB Output is correct
2 Correct 406 ms 61104 KB Output is correct
3 Correct 552 ms 78764 KB Output is correct
4 Correct 351 ms 60636 KB Output is correct
5 Correct 363 ms 61612 KB Output is correct
6 Correct 525 ms 78764 KB Output is correct
7 Correct 235 ms 78640 KB Output is correct
8 Correct 251 ms 76780 KB Output is correct
9 Correct 630 ms 78500 KB Output is correct
10 Correct 573 ms 78384 KB Output is correct
11 Correct 459 ms 78252 KB Output is correct
12 Correct 500 ms 78852 KB Output is correct
13 Correct 484 ms 78504 KB Output is correct
14 Correct 511 ms 78888 KB Output is correct
15 Correct 506 ms 78764 KB Output is correct
16 Correct 551 ms 79028 KB Output is correct
17 Correct 493 ms 78764 KB Output is correct
18 Correct 508 ms 78692 KB Output is correct
19 Correct 516 ms 78852 KB Output is correct
20 Correct 496 ms 78764 KB Output is correct
21 Correct 536 ms 79016 KB Output is correct
22 Correct 589 ms 78760 KB Output is correct
23 Correct 555 ms 78852 KB Output is correct
24 Correct 586 ms 79028 KB Output is correct
25 Correct 482 ms 77512 KB Output is correct
26 Correct 463 ms 78504 KB Output is correct
27 Correct 399 ms 78312 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 5 ms 13144 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 13148 KB Output is correct
8 Correct 7 ms 13148 KB Output is correct
9 Correct 6 ms 13148 KB Output is correct
10 Correct 6 ms 13148 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Correct 5 ms 13328 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13148 KB Output is correct
17 Correct 5 ms 13148 KB Output is correct
18 Correct 6 ms 13148 KB Output is correct
19 Correct 6 ms 13148 KB Output is correct
20 Correct 6 ms 13148 KB Output is correct
21 Correct 74 ms 29788 KB Output is correct
22 Correct 73 ms 29780 KB Output is correct
23 Correct 91 ms 29756 KB Output is correct
24 Correct 68 ms 29808 KB Output is correct
25 Correct 76 ms 29788 KB Output is correct
26 Correct 81 ms 29788 KB Output is correct
27 Correct 43 ms 28540 KB Output is correct
28 Correct 48 ms 29292 KB Output is correct
29 Correct 77 ms 29784 KB Output is correct
30 Correct 79 ms 29788 KB Output is correct
31 Correct 73 ms 29792 KB Output is correct
32 Correct 69 ms 29788 KB Output is correct
33 Correct 73 ms 28036 KB Output is correct
34 Correct 81 ms 29780 KB Output is correct
35 Correct 78 ms 29656 KB Output is correct
36 Correct 73 ms 29784 KB Output is correct
37 Correct 96 ms 28040 KB Output is correct
38 Correct 77 ms 26304 KB Output is correct
39 Correct 45 ms 26812 KB Output is correct
40 Correct 53 ms 28868 KB Output is correct
41 Correct 91 ms 29784 KB Output is correct
42 Correct 98 ms 29788 KB Output is correct
43 Correct 99 ms 29784 KB Output is correct
44 Correct 110 ms 29800 KB Output is correct
45 Correct 102 ms 29788 KB Output is correct
46 Correct 129 ms 29784 KB Output is correct
47 Correct 68 ms 29536 KB Output is correct
48 Correct 90 ms 29756 KB Output is correct
49 Correct 71 ms 24848 KB Output is correct
50 Correct 102 ms 27292 KB Output is correct
51 Correct 99 ms 29780 KB Output is correct
52 Correct 100 ms 29856 KB Output is correct
53 Correct 59 ms 26060 KB Output is correct
54 Correct 76 ms 29904 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 28044 KB Output is correct
2 Correct 113 ms 29528 KB Output is correct
3 Correct 115 ms 29784 KB Output is correct
4 Correct 75 ms 24820 KB Output is correct
5 Correct 103 ms 27544 KB Output is correct
6 Correct 110 ms 29784 KB Output is correct
7 Correct 62 ms 27800 KB Output is correct
8 Correct 67 ms 26792 KB Output is correct
9 Correct 81 ms 29036 KB Output is correct
10 Correct 64 ms 24312 KB Output is correct
11 Correct 97 ms 29408 KB Output is correct
12 Correct 118 ms 29268 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 5 ms 13144 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 13148 KB Output is correct
8 Correct 7 ms 13148 KB Output is correct
9 Correct 6 ms 13148 KB Output is correct
10 Correct 6 ms 13148 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Correct 5 ms 13328 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13148 KB Output is correct
17 Correct 5 ms 13148 KB Output is correct
18 Correct 6 ms 13148 KB Output is correct
19 Correct 6 ms 13148 KB Output is correct
20 Correct 6 ms 13148 KB Output is correct
21 Correct 6 ms 13148 KB Output is correct
22 Correct 6 ms 13144 KB Output is correct
23 Correct 5 ms 13148 KB Output is correct
24 Correct 8 ms 13144 KB Output is correct
25 Correct 5 ms 13148 KB Output is correct
26 Correct 5 ms 13148 KB Output is correct
27 Correct 6 ms 13256 KB Output is correct
28 Correct 6 ms 13148 KB Output is correct
29 Correct 6 ms 13148 KB Output is correct
30 Correct 5 ms 13148 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 5 ms 13400 KB Output is correct
33 Correct 5 ms 13148 KB Output is correct
34 Correct 5 ms 13280 KB Output is correct
35 Correct 5 ms 13148 KB Output is correct
36 Correct 5 ms 13336 KB Output is correct
37 Correct 6 ms 13144 KB Output is correct
38 Correct 6 ms 13148 KB Output is correct
39 Correct 74 ms 29788 KB Output is correct
40 Correct 73 ms 29780 KB Output is correct
41 Correct 91 ms 29756 KB Output is correct
42 Correct 68 ms 29808 KB Output is correct
43 Correct 76 ms 29788 KB Output is correct
44 Correct 81 ms 29788 KB Output is correct
45 Correct 43 ms 28540 KB Output is correct
46 Correct 48 ms 29292 KB Output is correct
47 Correct 77 ms 29784 KB Output is correct
48 Correct 79 ms 29788 KB Output is correct
49 Correct 73 ms 29792 KB Output is correct
50 Correct 69 ms 29788 KB Output is correct
51 Correct 73 ms 28036 KB Output is correct
52 Correct 81 ms 29780 KB Output is correct
53 Correct 78 ms 29656 KB Output is correct
54 Correct 73 ms 29784 KB Output is correct
55 Correct 96 ms 28040 KB Output is correct
56 Correct 77 ms 26304 KB Output is correct
57 Correct 45 ms 26812 KB Output is correct
58 Correct 53 ms 28868 KB Output is correct
59 Correct 91 ms 29784 KB Output is correct
60 Correct 98 ms 29788 KB Output is correct
61 Correct 99 ms 29784 KB Output is correct
62 Correct 110 ms 29800 KB Output is correct
63 Correct 102 ms 29788 KB Output is correct
64 Correct 129 ms 29784 KB Output is correct
65 Correct 68 ms 29536 KB Output is correct
66 Correct 90 ms 29756 KB Output is correct
67 Correct 71 ms 24848 KB Output is correct
68 Correct 102 ms 27292 KB Output is correct
69 Correct 99 ms 29780 KB Output is correct
70 Correct 100 ms 29856 KB Output is correct
71 Correct 59 ms 26060 KB Output is correct
72 Correct 76 ms 29904 KB Output is correct
73 Correct 105 ms 28044 KB Output is correct
74 Correct 113 ms 29528 KB Output is correct
75 Correct 115 ms 29784 KB Output is correct
76 Correct 75 ms 24820 KB Output is correct
77 Correct 103 ms 27544 KB Output is correct
78 Correct 110 ms 29784 KB Output is correct
79 Correct 62 ms 27800 KB Output is correct
80 Correct 67 ms 26792 KB Output is correct
81 Correct 81 ms 29036 KB Output is correct
82 Correct 64 ms 24312 KB Output is correct
83 Correct 97 ms 29408 KB Output is correct
84 Correct 118 ms 29268 KB Output is correct
85 Correct 98 ms 28292 KB Output is correct
86 Correct 105 ms 29792 KB Output is correct
87 Correct 95 ms 27548 KB Output is correct
88 Correct 103 ms 29780 KB Output is correct
89 Correct 62 ms 24312 KB Output is correct
90 Correct 98 ms 29788 KB Output is correct
91 Correct 82 ms 26804 KB Output is correct
92 Correct 80 ms 26104 KB Output is correct
93 Correct 106 ms 29844 KB Output is correct
94 Correct 104 ms 29788 KB Output is correct
95 Correct 102 ms 29532 KB Output is correct
96 Correct 102 ms 29792 KB Output is correct
97 Correct 99 ms 29888 KB Output is correct
98 Correct 90 ms 27304 KB Output is correct
99 Correct 73 ms 29536 KB Output is correct
100 Correct 81 ms 26868 KB Output is correct
101 Correct 92 ms 29844 KB Output is correct
102 Correct 77 ms 29720 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Correct 5 ms 13148 KB Output is correct
3 Correct 5 ms 13144 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 13148 KB Output is correct
8 Correct 7 ms 13148 KB Output is correct
9 Correct 6 ms 13148 KB Output is correct
10 Correct 6 ms 13148 KB Output is correct
11 Correct 5 ms 13148 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Correct 5 ms 13328 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13148 KB Output is correct
17 Correct 5 ms 13148 KB Output is correct
18 Correct 6 ms 13148 KB Output is correct
19 Correct 6 ms 13148 KB Output is correct
20 Correct 6 ms 13148 KB Output is correct
21 Correct 6 ms 13148 KB Output is correct
22 Correct 6 ms 13144 KB Output is correct
23 Correct 5 ms 13148 KB Output is correct
24 Correct 8 ms 13144 KB Output is correct
25 Correct 5 ms 13148 KB Output is correct
26 Correct 5 ms 13148 KB Output is correct
27 Correct 6 ms 13256 KB Output is correct
28 Correct 6 ms 13148 KB Output is correct
29 Correct 6 ms 13148 KB Output is correct
30 Correct 5 ms 13148 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 5 ms 13400 KB Output is correct
33 Correct 5 ms 13148 KB Output is correct
34 Correct 5 ms 13280 KB Output is correct
35 Correct 5 ms 13148 KB Output is correct
36 Correct 5 ms 13336 KB Output is correct
37 Correct 6 ms 13144 KB Output is correct
38 Correct 6 ms 13148 KB Output is correct
39 Correct 74 ms 29788 KB Output is correct
40 Correct 73 ms 29780 KB Output is correct
41 Correct 91 ms 29756 KB Output is correct
42 Correct 68 ms 29808 KB Output is correct
43 Correct 76 ms 29788 KB Output is correct
44 Correct 81 ms 29788 KB Output is correct
45 Correct 43 ms 28540 KB Output is correct
46 Correct 48 ms 29292 KB Output is correct
47 Correct 77 ms 29784 KB Output is correct
48 Correct 79 ms 29788 KB Output is correct
49 Correct 73 ms 29792 KB Output is correct
50 Correct 69 ms 29788 KB Output is correct
51 Correct 73 ms 28036 KB Output is correct
52 Correct 81 ms 29780 KB Output is correct
53 Correct 78 ms 29656 KB Output is correct
54 Correct 73 ms 29784 KB Output is correct
55 Correct 521 ms 73308 KB Output is correct
56 Correct 406 ms 61104 KB Output is correct
57 Correct 552 ms 78764 KB Output is correct
58 Correct 351 ms 60636 KB Output is correct
59 Correct 363 ms 61612 KB Output is correct
60 Correct 525 ms 78764 KB Output is correct
61 Correct 235 ms 78640 KB Output is correct
62 Correct 251 ms 76780 KB Output is correct
63 Correct 630 ms 78500 KB Output is correct
64 Correct 573 ms 78384 KB Output is correct
65 Correct 459 ms 78252 KB Output is correct
66 Correct 500 ms 78852 KB Output is correct
67 Correct 484 ms 78504 KB Output is correct
68 Correct 511 ms 78888 KB Output is correct
69 Correct 506 ms 78764 KB Output is correct
70 Correct 551 ms 79028 KB Output is correct
71 Correct 493 ms 78764 KB Output is correct
72 Correct 508 ms 78692 KB Output is correct
73 Correct 516 ms 78852 KB Output is correct
74 Correct 496 ms 78764 KB Output is correct
75 Correct 536 ms 79016 KB Output is correct
76 Correct 589 ms 78760 KB Output is correct
77 Correct 555 ms 78852 KB Output is correct
78 Correct 586 ms 79028 KB Output is correct
79 Correct 482 ms 77512 KB Output is correct
80 Correct 463 ms 78504 KB Output is correct
81 Correct 399 ms 78312 KB Output is correct
82 Correct 96 ms 28040 KB Output is correct
83 Correct 77 ms 26304 KB Output is correct
84 Correct 45 ms 26812 KB Output is correct
85 Correct 53 ms 28868 KB Output is correct
86 Correct 91 ms 29784 KB Output is correct
87 Correct 98 ms 29788 KB Output is correct
88 Correct 99 ms 29784 KB Output is correct
89 Correct 110 ms 29800 KB Output is correct
90 Correct 102 ms 29788 KB Output is correct
91 Correct 129 ms 29784 KB Output is correct
92 Correct 68 ms 29536 KB Output is correct
93 Correct 90 ms 29756 KB Output is correct
94 Correct 71 ms 24848 KB Output is correct
95 Correct 102 ms 27292 KB Output is correct
96 Correct 99 ms 29780 KB Output is correct
97 Correct 100 ms 29856 KB Output is correct
98 Correct 59 ms 26060 KB Output is correct
99 Correct 76 ms 29904 KB Output is correct
100 Correct 105 ms 28044 KB Output is correct
101 Correct 113 ms 29528 KB Output is correct
102 Correct 115 ms 29784 KB Output is correct
103 Correct 75 ms 24820 KB Output is correct
104 Correct 103 ms 27544 KB Output is correct
105 Correct 110 ms 29784 KB Output is correct
106 Correct 62 ms 27800 KB Output is correct
107 Correct 67 ms 26792 KB Output is correct
108 Correct 81 ms 29036 KB Output is correct
109 Correct 64 ms 24312 KB Output is correct
110 Correct 97 ms 29408 KB Output is correct
111 Correct 118 ms 29268 KB Output is correct
112 Correct 98 ms 28292 KB Output is correct
113 Correct 105 ms 29792 KB Output is correct
114 Correct 95 ms 27548 KB Output is correct
115 Correct 103 ms 29780 KB Output is correct
116 Correct 62 ms 24312 KB Output is correct
117 Correct 98 ms 29788 KB Output is correct
118 Correct 82 ms 26804 KB Output is correct
119 Correct 80 ms 26104 KB Output is correct
120 Correct 106 ms 29844 KB Output is correct
121 Correct 104 ms 29788 KB Output is correct
122 Correct 102 ms 29532 KB Output is correct
123 Correct 102 ms 29792 KB Output is correct
124 Correct 99 ms 29888 KB Output is correct
125 Correct 90 ms 27304 KB Output is correct
126 Correct 73 ms 29536 KB Output is correct
127 Correct 81 ms 26868 KB Output is correct
128 Correct 92 ms 29844 KB Output is correct
129 Correct 77 ms 29720 KB Output is correct
130 Correct 576 ms 79020 KB Output is correct
131 Correct 392 ms 60864 KB Output is correct
132 Correct 579 ms 79016 KB Output is correct
133 Correct 491 ms 76032 KB Output is correct
134 Correct 468 ms 69236 KB Output is correct
135 Correct 508 ms 79016 KB Output is correct
136 Correct 617 ms 78764 KB Output is correct
137 Correct 590 ms 78976 KB Output is correct
138 Correct 502 ms 78680 KB Output is correct
139 Correct 520 ms 78988 KB Output is correct
140 Correct 495 ms 78764 KB Output is correct
141 Correct 530 ms 79020 KB Output is correct
142 Correct 533 ms 79020 KB Output is correct
143 Correct 548 ms 79016 KB Output is correct
144 Correct 510 ms 79016 KB Output is correct
145 Correct 538 ms 79020 KB Output is correct
146 Correct 563 ms 79016 KB Output is correct
147 Correct 540 ms 79344 KB Output is correct
148 Correct 584 ms 79104 KB Output is correct
149 Correct 621 ms 78988 KB Output is correct
150 Correct 336 ms 77740 KB Output is correct
151 Correct 486 ms 78820 KB Output is correct
152 Correct 478 ms 78768 KB Output is correct
153 Correct 398 ms 78504 KB Output is correct