Submission #886336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886336	2023-12-11T22:18:37 Z	Kutan	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	507 ms	52336 KB

Main

// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));

const int INF = 1e9 , mod = 1e9 + 7;

template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }

template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }

template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }

#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}

typedef long long ll;
typedef double db;
const int N = 2e5 + 5;
const int maxQ = 1e6 + 5;
int n, q;
int a[N], b[N], ans[maxQ];
int nxt[N];

pair<pii, int> Query[maxQ];
void readip(){
    cin >> n >> q;
    REP(i, 1, n) cin >> a[i];

    REP(i, 1, q) cin >> Query[i].first.fi >> Query[i].first.se, Query[i].second = i;
    sort(Query + 1, Query + q + 1);


    vi st;
    REPD(i, n, 1) {
        while(!st.empty() && a[st.back()] < a[i]) st.pop_back();
        if (st.empty()) nxt[i] = n + 1;
        else nxt[i] = st.back();
        st.eb(i);
    }
}

namespace sub1{
    bool shuff() {
        int lpt = 1, rpt = n / 2 + 1;
        int cnt = 0;
        for (; lpt <= n / 2; ++lpt) {
            while(rpt <= n && a[rpt] < a[lpt]) 
                b[++cnt] = a[rpt++];
            b[++cnt] = a[lpt];
        }
        while(rpt <= n) b[++cnt] = a[rpt++];

        bool res = 0;
        REP(i, 1, n) if (a[i] != b[i]) {
            res = 1;
            a[i] = b[i];
        }
        return res;
    }

    void solve() {
        int cnt = 0, qid = 1;
        do {
            while(qid <= q && Query[qid].first.fi == cnt) {
                ans[Query[qid].se] = a[Query[qid].first.se];
                ++qid;
            }
            ++cnt;
            if (cnt > Query[q].first.fi) break;
        } while(shuff());
        while(qid <= q) ans[Query[qid].se] = a[Query[qid].fi.se], ++qid;
        REP(i, 1, q) cout << ans[i] << ln;
    }
};

struct Data{
    int val, l, r;
    Data(int _val = 0, int _l = 0, int _r = 0) {
        val = _val, l = _l, r = _r;
    }
    bool operator < (const Data other) const {
        return val < other.val;
    }
};    set<Data> s;


namespace sub2{
    void solve() {
        int i = 1;
        while(i <= n) s.insert(Data(a[i], i, nxt[i] - 1)), i = nxt[i];

        int rpt = n, total_size = n, cnt = 0;
        while(cnt < Query[1].fi.fi) {
            while(!s.empty()) {
                auto it = s.end(); --it;
                if (total_size - (it->r - it->l + 1) >= n / 2) {
                    REPD(i, it->r, it->l) b[rpt--] = a[i];
                    total_size -= (it->r - it->l + 1);
                    s.erase(it);
                }
                else break;
            }

            if (total_size == n / 2) break;
            ++cnt;

            auto it = s.end(); --it;
            int v = it->val, l = it->l, r = it->r;
            s.erase(it);

            int pref_size = total_size - (r - l + 1);
            int lef_size = n / 2 - pref_size;
            s.insert(Data(v, l, l + lef_size - 1));

            int i = l + lef_size;
            while(i <= r) {
                s.insert(Data(a[i], i, min(r, nxt[i] - 1)));
                i = nxt[i];
            }
        }   
        while(!s.empty()) {
            auto it = s.end(); --it;
            REPD(i, it->r, it->l) b[rpt--] = a[i];
            s.erase(it);
        }

        REP(i, 1, q) ans[Query[i].se] = b[Query[i].fi.se];
        REP(i, 1, q) cout << ans[i] << ln;
    }
};

namespace subfull{
    struct segtree{
        int it[N << 2];
        void upd(int i, int val, int id = 1, int l = 1, int r = n) {
            if (l == r) {
                it[id] = val;
                return;
            }
            int mid = (l + r) >> 1;
            if (i <= mid) upd(i, val, id << 1, l, mid);
            else upd(i, val, id << 1 | 1, mid + 1, r);
            it[id] = it[id << 1] + it[id << 1 | 1];
        }

        int get(int u, int v, int id = 1, int l = 1, int r = n) {
            if (u <= l && r <= v) return it[id];
            int mid = (l + r) >> 1;
            int res(0);
            if (u <= mid) res += get(u, v, id << 1, l, mid);
            if (v > mid) res += get(u, v, id << 1 | 1, mid + 1, r);
            return res;
        }

        int walk(int val) {
            int id = 1, l = 1, r = n, res = n;
            while(1) {
                if (l == r) return (it[id] >= val ? l : res);
                int mid = (l + r) >> 1;
                if (it[id << 1] >= val) {
                    res = mid;
                    r = mid;
                    id = id << 1;
                }
                else {
                    val -= it[id << 1];
                    l = mid + 1;
                    id = id << 1 | 1;
                }
            }
        }
    } ST;

    int curL[N], curR[N];

    void solve() {
        for (int i = 1; i <= n; i = nxt[i]) {
            s.insert(Data(a[i], i, nxt[i] - 1));
            ST.upd(a[i], nxt[i] - i);

            curL[a[i]] = i;
            curR[a[i]] = nxt[i] - 1;
        }

        int qid = 1, rpt = n, total_size = n;
        while(qid <= q && Query[qid].fi.fi == 0) {
            ans[Query[qid].se] = a[Query[qid].fi.se];
            ++qid;
        }

        REP(Time, 1, n) {
            while(!s.empty()) {
                auto it = s.end(); --it;
                if (total_size - (it->r - it->l + 1) >= n / 2) {
                    REPD(i, it->r, it->l) b[rpt--] = a[i];
                    total_size -= (it->r - it->l + 1);
                    ST.upd(it -> val, 0);
                    s.erase(it);
                }
                else break;
            }
            if (total_size == n / 2) break;

            auto it = s.end(); --it;
            int v = it->val, l = it->l, r = it->r;
            s.erase(it);
            ST.upd(v, 0);

            int pref_size = total_size - (r - l + 1);
            int lef_size = n / 2 - pref_size;
            s.insert(Data(v, l, l + lef_size - 1));
            ST.upd(v, lef_size);
            curL[v] = l, curR[v] = l + lef_size - 1;

            int i = l + lef_size;
            while(i <= r) {
                s.insert(Data(a[i], i, min(r, nxt[i] - 1)));
                ST.upd(a[i], min(r, nxt[i] - 1) - i + 1);
                curL[a[i]] = i, curR[a[i]] = min(r, nxt[i] - 1);
                i = nxt[i];
            }

            while(qid <= q && Query[qid].first.fi == Time) {
                if (Query[qid].first.se > total_size) {
                    // cout << "wtf " << Query[qid].first.se << ' ' << rpt << ln; 
                    ans[Query[qid].second] = b[Query[qid].first.se];
                }
                else {
                    int val = ST.walk(Query[qid].first.se);
                    int prefsize = (val == 1 ? 0 : ST.get(1, val - 1));
                    ans[Query[qid].second] = a[curL[val] + Query[qid].first.se - prefsize - 1];
                }
                ++qid;
            }
        }   

        while(!s.empty()) {
            auto it = s.end(); --it;
            REPD(i, it->r, it->l) b[rpt--] = a[i];
            s.erase(it);
        }

        while(qid <= q) {
            ans[Query[qid].se] = b[Query[qid].first.se];
            ++qid;
        }
        REP(i, 1, q) cout << ans[i] << ln;
    }
};

void solve(){   
    // if (n <= 1000) {
    //     sub1::solve();
    //     return;
    // }
    // if (Query[1].fi.fi == Query[q].fi.fi) {
    //     sub2::solve();
    //     return;
    // }
    subfull::solve();
}

int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

Main.cpp: In function 'void readip()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:146:5: note: in expansion of macro 'REP'
  146 |     REP(i, 1, n) cin >> a[i];
      |     ^~~
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:148:5: note: in expansion of macro 'REP'
  148 |     REP(i, 1, q) cin >> Query[i].first.fi >> Query[i].first.se, Query[i].second = i;
      |     ^~~
Main.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
Main.cpp:153:5: note: in expansion of macro 'REPD'
  153 |     REPD(i, n, 1) {
      |     ^~~~
Main.cpp: In function 'bool sub1::shuff()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:173:9: note: in expansion of macro 'REP'
  173 |         REP(i, 1, n) if (a[i] != b[i]) {
      |         ^~~
Main.cpp: In function 'void sub1::solve()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:191:9: note: in expansion of macro 'REP'
  191 |         REP(i, 1, q) cout << ans[i] << ln;
      |         ^~~
Main.cpp: In function 'void sub2::solve()':
Main.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
Main.cpp:216:21: note: in expansion of macro 'REPD'
  216 |                     REPD(i, it->r, it->l) b[rpt--] = a[i];
      |                     ^~~~
Main.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
Main.cpp:242:13: note: in expansion of macro 'REPD'
  242 |             REPD(i, it->r, it->l) b[rpt--] = a[i];
      |             ^~~~
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:246:9: note: in expansion of macro 'REP'
  246 |         REP(i, 1, q) ans[Query[i].se] = b[Query[i].fi.se];
      |         ^~~
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:247:9: note: in expansion of macro 'REP'
  247 |         REP(i, 1, q) cout << ans[i] << ln;
      |         ^~~
Main.cpp: In function 'void subfull::solve()':
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'Time' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:310:9: note: in expansion of macro 'REP'
  310 |         REP(Time, 1, n) {
      |         ^~~
Main.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
Main.cpp:314:21: note: in expansion of macro 'REPD'
  314 |                     REPD(i, it->r, it->l) b[rpt--] = a[i];
      |                     ^~~~
Main.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
Main.cpp:358:13: note: in expansion of macro 'REPD'
  358 |             REPD(i, it->r, it->l) b[rpt--] = a[i];
      |             ^~~~
Main.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
Main.cpp:366:9: note: in expansion of macro 'REP'
  366 |         REP(i, 1, q) cout << ans[i] << ln;
      |         ^~~
Main.cpp: In function 'void file()':
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	277 ms	30940 KB	Output is correct
2	Correct	294 ms	30664 KB	Output is correct
3	Correct	287 ms	30256 KB	Output is correct
4	Correct	283 ms	28856 KB	Output is correct
5	Correct	279 ms	30292 KB	Output is correct
6	Correct	267 ms	29384 KB	Output is correct
7	Correct	285 ms	30296 KB	Output is correct
8	Correct	263 ms	29440 KB	Output is correct
9	Correct	278 ms	29320 KB	Output is correct
10	Correct	268 ms	29528 KB	Output is correct
11	Correct	275 ms	29256 KB	Output is correct
12	Correct	262 ms	28456 KB	Output is correct
13	Correct	290 ms	29204 KB	Output is correct
14	Correct	286 ms	29776 KB	Output is correct
15	Correct	295 ms	29576 KB	Output is correct
16	Correct	1 ms	8536 KB	Output is correct
17	Correct	231 ms	28736 KB	Output is correct
18	Correct	265 ms	28364 KB	Output is correct
19	Correct	1 ms	8540 KB	Output is correct
20	Correct	1 ms	8536 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	50160 KB	Output is correct
2	Correct	341 ms	52336 KB	Output is correct
3	Correct	326 ms	44300 KB	Output is correct
4	Correct	281 ms	41556 KB	Output is correct
5	Correct	292 ms	42312 KB	Output is correct
6	Correct	272 ms	41216 KB	Output is correct
7	Correct	309 ms	44536 KB	Output is correct
8	Correct	308 ms	44044 KB	Output is correct
9	Correct	270 ms	41420 KB	Output is correct
10	Correct	296 ms	41476 KB	Output is correct
11	Correct	251 ms	37184 KB	Output is correct
12	Correct	246 ms	38024 KB	Output is correct
13	Correct	281 ms	40252 KB	Output is correct
14	Correct	250 ms	38056 KB	Output is correct
15	Correct	290 ms	41812 KB	Output is correct
16	Correct	17 ms	13652 KB	Output is correct
17	Correct	262 ms	50216 KB	Output is correct
18	Correct	255 ms	34968 KB	Output is correct
19	Correct	55 ms	18368 KB	Output is correct
20	Correct	59 ms	20392 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	16976 KB	Output is correct
2	Correct	72 ms	18624 KB	Output is correct
3	Correct	85 ms	16876 KB	Output is correct
4	Correct	42 ms	14280 KB	Output is correct
5	Correct	62 ms	16736 KB	Output is correct
6	Correct	45 ms	14672 KB	Output is correct
7	Correct	54 ms	15688 KB	Output is correct
8	Correct	50 ms	15184 KB	Output is correct
9	Correct	70 ms	15944 KB	Output is correct
10	Correct	39 ms	13824 KB	Output is correct
11	Correct	40 ms	13900 KB	Output is correct
12	Correct	38 ms	13652 KB	Output is correct
13	Correct	42 ms	13904 KB	Output is correct
14	Correct	42 ms	13908 KB	Output is correct
15	Correct	38 ms	13660 KB	Output is correct
16	Correct	9 ms	12372 KB	Output is correct
17	Correct	58 ms	19276 KB	Output is correct
18	Correct	33 ms	11088 KB	Output is correct
19	Correct	1 ms	8536 KB	Output is correct
20	Correct	1 ms	8540 KB	Output is correct

Subtask #4

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	277 ms	30940 KB	Output is correct
2	Correct	294 ms	30664 KB	Output is correct
3	Correct	287 ms	30256 KB	Output is correct
4	Correct	283 ms	28856 KB	Output is correct
5	Correct	279 ms	30292 KB	Output is correct
6	Correct	267 ms	29384 KB	Output is correct
7	Correct	285 ms	30296 KB	Output is correct
8	Correct	263 ms	29440 KB	Output is correct
9	Correct	278 ms	29320 KB	Output is correct
10	Correct	268 ms	29528 KB	Output is correct
11	Correct	275 ms	29256 KB	Output is correct
12	Correct	262 ms	28456 KB	Output is correct
13	Correct	290 ms	29204 KB	Output is correct
14	Correct	286 ms	29776 KB	Output is correct
15	Correct	295 ms	29576 KB	Output is correct
16	Correct	1 ms	8536 KB	Output is correct
17	Correct	231 ms	28736 KB	Output is correct
18	Correct	265 ms	28364 KB	Output is correct
19	Correct	1 ms	8540 KB	Output is correct
20	Correct	1 ms	8536 KB	Output is correct
21	Correct	345 ms	50160 KB	Output is correct
22	Correct	341 ms	52336 KB	Output is correct
23	Correct	326 ms	44300 KB	Output is correct
24	Correct	281 ms	41556 KB	Output is correct
25	Correct	292 ms	42312 KB	Output is correct
26	Correct	272 ms	41216 KB	Output is correct
27	Correct	309 ms	44536 KB	Output is correct
28	Correct	308 ms	44044 KB	Output is correct
29	Correct	270 ms	41420 KB	Output is correct
30	Correct	296 ms	41476 KB	Output is correct
31	Correct	251 ms	37184 KB	Output is correct
32	Correct	246 ms	38024 KB	Output is correct
33	Correct	281 ms	40252 KB	Output is correct
34	Correct	250 ms	38056 KB	Output is correct
35	Correct	290 ms	41812 KB	Output is correct
36	Correct	17 ms	13652 KB	Output is correct
37	Correct	262 ms	50216 KB	Output is correct
38	Correct	255 ms	34968 KB	Output is correct
39	Correct	55 ms	18368 KB	Output is correct
40	Correct	59 ms	20392 KB	Output is correct
41	Correct	76 ms	16976 KB	Output is correct
42	Correct	72 ms	18624 KB	Output is correct
43	Correct	85 ms	16876 KB	Output is correct
44	Correct	42 ms	14280 KB	Output is correct
45	Correct	62 ms	16736 KB	Output is correct
46	Correct	45 ms	14672 KB	Output is correct
47	Correct	54 ms	15688 KB	Output is correct
48	Correct	50 ms	15184 KB	Output is correct
49	Correct	70 ms	15944 KB	Output is correct
50	Correct	39 ms	13824 KB	Output is correct
51	Correct	40 ms	13900 KB	Output is correct
52	Correct	38 ms	13652 KB	Output is correct
53	Correct	42 ms	13904 KB	Output is correct
54	Correct	42 ms	13908 KB	Output is correct
55	Correct	38 ms	13660 KB	Output is correct
56	Correct	9 ms	12372 KB	Output is correct
57	Correct	58 ms	19276 KB	Output is correct
58	Correct	33 ms	11088 KB	Output is correct
59	Correct	1 ms	8536 KB	Output is correct
60	Correct	1 ms	8540 KB	Output is correct
61	Correct	443 ms	49748 KB	Output is correct
62	Correct	463 ms	52204 KB	Output is correct
63	Correct	507 ms	47828 KB	Output is correct
64	Correct	389 ms	45544 KB	Output is correct
65	Correct	430 ms	46164 KB	Output is correct
66	Correct	390 ms	44628 KB	Output is correct
67	Correct	396 ms	44128 KB	Output is correct
68	Correct	405 ms	43860 KB	Output is correct
69	Correct	435 ms	44116 KB	Output is correct
70	Correct	386 ms	41556 KB	Output is correct
71	Correct	352 ms	40228 KB	Output is correct
72	Correct	360 ms	41248 KB	Output is correct
73	Correct	386 ms	40788 KB	Output is correct
74	Correct	384 ms	41796 KB	Output is correct
75	Correct	383 ms	41780 KB	Output is correct
76	Correct	19 ms	13648 KB	Output is correct
77	Correct	335 ms	50228 KB	Output is correct
78	Correct	350 ms	37972 KB	Output is correct
79	Correct	2 ms	8536 KB	Output is correct
80	Correct	1 ms	8540 KB	Output is correct