oj.uz

Submission #976826

# Submission time Handle Problem Language Result Execution time Memory
976826 2024-05-07T07:12:44 Z Nahian9696 Strange Device (APIO19_strange_device) C++17
100 / 100
 2220 ms 141896 KB 
#include <bits/stdc++.h>

using namespace std;



#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace __gnu_pbds;


template<typename dataType>
using ordered_set = tree<dataType, null_type, less<dataType>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename dataType1, typename dataType2>
using ordered_map = tree<dataType1, dataType2, less<dataType1>, rb_tree_tag, tree_order_statistics_node_update>;





typedef long double                         ld;
typedef unsigned                            ui;
typedef long long                           lli;
typedef unsigned long long                  ulli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<ui>                          vui;
typedef vector<lli>                         vlli;
typedef vector<ulli>                        vulli;
typedef list<int32_t>                       lsi;
typedef list<ld>                            lsld;
typedef list<ui>                            lsui;
typedef list<lli>                           lslli;
typedef list<ulli>                          lsulli;
typedef set<int32_t>                        si;
typedef set<ld>                             sld;
typedef set<ui>                             sui;
typedef set<lli>                            slli;
typedef set<ulli>                           sulli;

typedef pair<lli, lli>                      pii;
typedef pair<lli, lli>                      pll;



#define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define Inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define Inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second
#define maxi                                maximize
#define mini                                minimize   

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
template<typename dataType>
inline void maximize(dataType &a, dataType b) {if (a < b) a = b;}
template<typename dataType>
inline void minimize(dataType &a, dataType b) {if (a > b) a = b;}

template<typename dataType>
dataType partitionProbDiff(dataType* arr, dataType n) {
    dataType sum = 0;
    for (int32_t i = 0; i < n; i++) sum += arr[i];

    bool dp[n + 1][sum + 1];
    for (int32_t i = 0; i <= n; i++) dp[i][0] = true;
    for (int32_t i = 1; i <= sum; i++) dp[0][i] = false;

    for (int32_t i = 1; i <= n; i++) {
        for (int32_t j = 1; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];
 
            if (arr[i - 1] <= j)
                dp[i][j] |= dp[i - 1][j - arr[i - 1]];
        }
    }
    for (int32_t j = sum / 2; j >= 0; j--) {
        if (dp[n][j] == true) {
            return (sum - 2 * j);
        }
    }
}
template<typename dataType>
bool subsetSumProblem(dataType set[], dataType n, dataType sum) {
    bool subset[n + 1][sum + 1];
    for (int32_t i = 0; i <= n; i++)
        subset[i][0] = true;
    for (int32_t i = 1; i <= sum; i++)
        subset[0][i] = false;
    for (int32_t i = 1; i <= n; i++) {
        for (int32_t j = 1; j <= sum; j++) {
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
        }
    }
    return subset[n][sum];
}
bool isPrefix(string &s, string &y) {
    if(s.length() > y.length()) return false;
    f0(i, s.length()) if(s[i] != y[i]) return false;
    return true;
}
bool ispalindrom(string s) {
    f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
    return true;
}

template<typename dataType>
dataType gcd(dataType a, dataType b) {
    while (b != 0) {
        dataType c = b;
        b = (lli)a % (lli)b;
        a = c;
    }
    return a;
}


template<typename dataType>
void allPrimeBoolArray(dataType n, bool* prime) {
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType1 i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int32_t p = 2; p <= n; p++)
        if (prime[p])
            primeList.pb(p);
}

template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
    string s = bitset<64>(n).to_string();

    return s.substr(64-k);
}

template<typename dataType>
string decimalToBinary(dataType n) {
    string s = bitset<64>(n).to_string();

    const auto loc1 = s.find('1');

    if(loc1 != string::npos)
        return s.substr(loc1);
     
    return "0";
}

template<typename dataType>
dataType val(char c) {
    if (c >= '0' && c <= '9')
        return (dataType)c - '0';
    else
        return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
    int32_t len = str.length();
    int32_t power = 1;
    dataType num = 0;
 
    for (int32_t i = len - 1; i >= 0; i--) {
        num += (val<dataType>(str[i]) * power);
        power *= base;
    }

    return num;
}

template<typename dataType>
char reVal(dataType num) {
    if (num >= 0 && num <= 9)
        return (char)(num + '0');
    else
        return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
    string res = "";
    while (inputNum > 0) {
        res += reVal(inputNum % base);
        inputNum /= base;
    }
    if (res == "")
        res = "0";
    return revStr(res);
}


template<typename dataType1, typename dataType2>
dataType1 smallFactor(dataType1 n, dataType2 &primes) {
    for (dataType1 x:primes) {
        if(n % x == 0) {
            return x;
            break;
        } else if (x > sqrt(n)) {
            return n;
            break;
        }
    }
    return 7;
}

template<typename dataType>
dataType phi(dataType n) {
    dataType result = n;
    for(int32_t p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        int64_t t_pow = (int64_t)powMod(base, n/2, mod);
        return ((t_pow*t_pow) % mod);
    }
    int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
    return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
    if(isPrime) return powMod(n, mod-2, mod);
    return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
    return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}

//define a compare function for pair
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
bool compare(pair<dataType1, dataType2> &a, pair<dataType3, dataType4> &b) {
    return a.first < b.first;
}


template<typename dataType>
dataType segtree_operator(dataType a, dataType b) {
    return a + b;
}


template<typename dataType>
struct segtree {
    int size;
    vector<dataType> tree;
    dataType init_val;
    
    template<typename dataType1>
    segtree(int n, dataType1 &arr, dataType init) {
        init_segtree(n, init);
        for (int32_t i = 0; i < n; i++) {
            tree[size+i] = arr[i];
        }
        for (int32_t i = size-1; i > 0; i--) {
            tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
        }
    }

    segtree(int n, dataType* arr, dataType init) {
        init_segtree(n, init);
        for (int32_t i = 0; i < n; i++) {
            tree[size+i] = arr[i];
        }
        for (int32_t i = size-1; i > 0; i--) {
            tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
        }
    }

    void init_segtree(int n, dataType init) {
        size = 1;
        init_val = init;
        while (size < n) size *= 2;
        tree.resize(size*2, init_val);
    }

    void update(int ind, dataType val) {
        ind += size;
        tree[ind] = val;
        while (ind > 1) {
            ind /= 2;
            tree[ind] = segtree_operator(tree[ind*2], tree[ind*2+1]);
        }
    }

    dataType query(int l, int r) {
        l += size;
        r += size;
        dataType res = init_val;
        while (l <= r) {
            if (l % 2 == 1) res = segtree_operator(res, tree[l]);
            if (r % 2 == 0) res = segtree_operator(res, tree[r]);
            l = (l+1) / 2;
            r = (r-1) / 2;
        }
        return res;
    }
};

// Varriables & helper functions
int n;

int a, b, t;
set<pair<int,int>> ranges_lr, ranges_rl;
vector<pair<int,int>> ranges;
pair<int, int> process(int x, int y) {
    x %= t;
    y %= t;

    return {x, y};
}

// Solver functions

int32_t solve1(int32_t) {
    cin >> n >> a >> b;

    int k = a/gcd(a, b+1);

    if(ld(b) * ld(k) >= 2e18) {
        t = 2e18;
    } else t = b*k;

    // print(t);

    f0(i, n) {
        inp2(x, y);
        if(y - x >= t) {
            print(t);
            finish;
        }
        auto [l, r] = process(x, y);
        // print(l, r);
        if(l > r) {
            ranges_lr.insert({l, t-1});
            ranges_lr.insert({0, r});
            ranges_rl.insert({t-1, l});
            ranges_rl.insert({r, 0});
            ranges.pb({l, t});
            ranges.pb({0, r});
        } else {
            ranges_lr.insert({l, r});
            ranges_rl.insert({r, l});
            ranges.pb({l, r});
        }
    }
    asrt(ranges);

    for(auto [l, r]:ranges) {
        // print(l, r);
        if(ranges_lr.find({l, r}) == ranges_lr.end()) {
            continue;
        }

        set<pair<int,int>> temp;

        while(true) {
            bool have_l = true, have_r = true;
            auto it = ranges_lr.lower_bound({l, -INF});
            int cnt = 0;
            while(it != ranges_lr.end()) {
                if(it->first > r) {
                    break;
                }
                cnt++;
                maxi(r, it->second);
                temp.insert(*it);
                it++;
            }
            if(cnt == 0) {
                have_l = false;
            }

            it = ranges_rl.lower_bound({l, -INF});
            cnt = 0;
            while(it != ranges_rl.end()) {
                if(it->first > r) {
                    break;
                }
                cnt++;
                mini(l, it->second);
                temp.insert({it->second, it->first});
                it++;
            }
            if(cnt == 0) {
                have_r = false;
            }

            if(!have_l && !have_r) {
                break;
            }

            for(auto [ll, rr]:temp) {
                ranges_lr.erase({ll, rr});
                ranges_rl.erase({rr, ll});
            }
            temp.clear();
        }
        
        ranges_lr.insert({l, r});
        ranges_rl.insert({r, l});
    }

    int ans = 0;

    for(auto [l, r]:ranges_lr) {
        ans += r - l+1;
    }

    print(min(ans, t));
    finish;
}


int32_t solve2(int32_t);


int32_t solve3(int32_t);



int32_t main() {

    #if defined __has_include
        #if __has_include("LOCAL.hh")
            #include "LOCAL.hh"
        #endif
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    // Previous code



    // Main code
    int32_t test = 1;

    // testIn;

    tests {

        solve1(testNo);

    }
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
    finish;
}

Compilation message

strange_device.cpp: In function 'bool isPrefix(std::string&, std::string&)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
strange_device.cpp:168:5: note: in expansion of macro 'f0'
  168 |     f0(i, s.length()) if(s[i] != y[i]) return false;
      |     ^~
strange_device.cpp: In function 'bool ispalindrom(std::string)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
strange_device.cpp:172:5: note: in expansion of macro 'f0'
  172 |     f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 12 ms 1752 KB Output is correct
3 Correct 16 ms 1952 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 10 ms 1680 KB Output is correct
17 Correct 160 ms 14664 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 301 ms 17352 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1798 ms 141568 KB Output is correct
3 Correct 1916 ms 141476 KB Output is correct
4 Correct 1977 ms 141252 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1798 ms 141568 KB Output is correct
3 Correct 1916 ms 141476 KB Output is correct
4 Correct 1977 ms 141252 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1830 ms 141896 KB Output is correct
7 Correct 1925 ms 141756 KB Output is correct
8 Correct 1839 ms 141220 KB Output is correct
9 Correct 2145 ms 141120 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1798 ms 141568 KB Output is correct
3 Correct 1916 ms 141476 KB Output is correct
4 Correct 1977 ms 141252 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 154 ms 14436 KB Output is correct
7 Correct 125 ms 14500 KB Output is correct
8 Correct 136 ms 14356 KB Output is correct
9 Correct 154 ms 14532 KB Output is correct
10 Correct 120 ms 14536 KB Output is correct
11 Correct 125 ms 14532 KB Output is correct
12 Correct 132 ms 14524 KB Output is correct
13 Correct 185 ms 14524 KB Output is correct
14 Correct 119 ms 14296 KB Output is correct
15 Correct 189 ms 14536 KB Output is correct
16 Correct 171 ms 14404 KB Output is correct
17 Correct 152 ms 14520 KB Output is correct
18 Correct 1767 ms 141288 KB Output is correct
19 Correct 1969 ms 141220 KB Output is correct
20 Correct 2193 ms 141432 KB Output is correct
21 Correct 140 ms 14524 KB Output is correct
22 Correct 142 ms 14480 KB Output is correct
23 Correct 124 ms 10556 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 167 ms 14432 KB Output is correct
3 Correct 169 ms 14528 KB Output is correct
4 Correct 2037 ms 141236 KB Output is correct
5 Correct 177 ms 14360 KB Output is correct
6 Correct 172 ms 14380 KB Output is correct
7 Correct 174 ms 14532 KB Output is correct
8 Correct 180 ms 14528 KB Output is correct
9 Correct 162 ms 14288 KB Output is correct
10 Correct 144 ms 14524 KB Output is correct
11 Correct 148 ms 14528 KB Output is correct
12 Correct 155 ms 14488 KB Output is correct
13 Correct 176 ms 14532 KB Output is correct
14 Correct 2217 ms 141292 KB Output is correct
15 Correct 128 ms 14304 KB Output is correct
16 Correct 1808 ms 141356 KB Output is correct
17 Correct 1828 ms 141132 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 12 ms 1752 KB Output is correct
3 Correct 16 ms 1952 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 10 ms 1680 KB Output is correct
17 Correct 160 ms 14664 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 301 ms 17352 KB Output is correct
29 Correct 0 ms 600 KB Output is correct
30 Correct 1798 ms 141568 KB Output is correct
31 Correct 1916 ms 141476 KB Output is correct
32 Correct 1977 ms 141252 KB Output is correct
33 Correct 0 ms 600 KB Output is correct
34 Correct 1830 ms 141896 KB Output is correct
35 Correct 1925 ms 141756 KB Output is correct
36 Correct 1839 ms 141220 KB Output is correct
37 Correct 2145 ms 141120 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 154 ms 14436 KB Output is correct
40 Correct 125 ms 14500 KB Output is correct
41 Correct 136 ms 14356 KB Output is correct
42 Correct 154 ms 14532 KB Output is correct
43 Correct 120 ms 14536 KB Output is correct
44 Correct 125 ms 14532 KB Output is correct
45 Correct 132 ms 14524 KB Output is correct
46 Correct 185 ms 14524 KB Output is correct
47 Correct 119 ms 14296 KB Output is correct
48 Correct 189 ms 14536 KB Output is correct
49 Correct 171 ms 14404 KB Output is correct
50 Correct 152 ms 14520 KB Output is correct
51 Correct 1767 ms 141288 KB Output is correct
52 Correct 1969 ms 141220 KB Output is correct
53 Correct 2193 ms 141432 KB Output is correct
54 Correct 140 ms 14524 KB Output is correct
55 Correct 142 ms 14480 KB Output is correct
56 Correct 124 ms 10556 KB Output is correct
57 Correct 1 ms 344 KB Output is correct
58 Correct 167 ms 14432 KB Output is correct
59 Correct 169 ms 14528 KB Output is correct
60 Correct 2037 ms 141236 KB Output is correct
61 Correct 177 ms 14360 KB Output is correct
62 Correct 172 ms 14380 KB Output is correct
63 Correct 174 ms 14532 KB Output is correct
64 Correct 180 ms 14528 KB Output is correct
65 Correct 162 ms 14288 KB Output is correct
66 Correct 144 ms 14524 KB Output is correct
67 Correct 148 ms 14528 KB Output is correct
68 Correct 155 ms 14488 KB Output is correct
69 Correct 176 ms 14532 KB Output is correct
70 Correct 2217 ms 141292 KB Output is correct
71 Correct 128 ms 14304 KB Output is correct
72 Correct 1808 ms 141356 KB Output is correct
73 Correct 1828 ms 141132 KB Output is correct
74 Correct 0 ms 344 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 12 ms 1752 KB Output is correct
80 Correct 2129 ms 141360 KB Output is correct
81 Correct 2039 ms 141420 KB Output is correct
82 Correct 2161 ms 141536 KB Output is correct
83 Correct 2161 ms 141308 KB Output is correct
84 Correct 2220 ms 141348 KB Output is correct
85 Correct 2152 ms 141408 KB Output is correct
86 Correct 122 ms 8648 KB Output is correct
87 Correct 0 ms 348 KB Output is correct