oj.uz

답안 #1102152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102152 2024-10-17T14:48:33 Z Requiem 가로등 (APIO19_street_lamps) C++17
80 / 100
 949 ms 374772 KB 
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Street lamp:

Có n trạm dừng kết nối n + 1 cái stop.
ta biết trạng thái của cái stop

Ta có q truy vấn:
- query a b: Từ 1 đến i, ta, tổng các thời điểm mà ta có thể đi từ a b
- toggle i: lật ngược vị trí i

subtask 1: n <= 100, q <= 100. Chạy n * q^2.

subtask 2: b = a + 1.
Tức là ta chỉ quan tâm vị trí i được bật bao nhiêu lần.
cái này bỏ vào prefix sum.

subtask 3: Khi bật nút i, nó sẽ luôn bật.
Nó là bài toán dsu điển hình, tức là 2 đỉnh sẽ không bao giờ bị disconnect.

subtask 4:
Ta toggle trước xong mới đến các truy vấn.
Giả sử ta dsu rollback, khi ta thêm 1 cạnh vào, nó
sẽ liên kết các tplt bên trong đó.

Giả sử nó nối đoạn [1...3] với [4..5] thì ta thêm hình chữ nhật [1...3], [4...5]
với trọng số là thời gian t.

Khi này ta sẽ tính offline bằng sweepline. Giả sử ta cần truy vấn a, b: thì ta chỉ cần truy vấn đoạn [a, b].
Ta có n log n sự kiện thì có tối đa n log n hình chữ nhật,

subtask 5:
Bây giờ ta cần phải xử lý online. Làm thế nào cơ chứ.
Nếu ta cắm BIT2D vào thì nó cũng vẫn sẽ là N log ^ 3 N.
Ta chia các hcn thành 2 loại:
- Đã kết thúc
- Còn thời gian.
**/

const int MAXN = 3e5 + 9;
int n, q, u, v;
char lamp[MAXN];

struct query{
    string type;
    int l, r, u;
} Query[MAXN];

struct DSU{
    struct DSUnode{
        int par;
        int sz;
        int mn;
        int mx;
    };
    vector<DSUnode> D;
    vector<array<int, 6>> changes;
    int small_to_large, path_compression, roll_back;
    DSU(int sz = 0, int _small_to_large = 1, int _path_compression = 1, int _roll_back = 0){
        D.resize(sz + 9);
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        roll_back = _roll_back;
        FOR(i, 0, D.size() - 1){
            D[i].par = i;
            D[i].sz = 1;
            D[i].mn = D[i].mx = i;
        }
    }

    void rollback(){
        if (changes.size() == 0) return;
        array<int, 6> tp = changes.back();
        int u = tp[0];
        int v = tp[1];
        D[u].sz -= D[v].sz;
        D[v].par = v;
        D[u].mn = tp[2], D[u].mx = tp[3];
        D[v].mn = tp[4], D[v].mx = tp[5];
        changes.pop_back();
    }
    int root(int u){
        if (D[u].par == u) return u;
        else {
            int p = root(D[u].par);
            if (path_compression) D[u].par = p;
            return p;
        }
    }

    bool unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (small_to_large and D[u].sz < D[v].sz) swap(u, v);
            D[u].sz += D[v].sz;
            D[v].par = u;
            if (roll_back) changes.pb({u, v, D[u].mn, D[u].mx, D[v].mn, D[v].mx});;

            D[u].mx = max(D[u].mx, D[v].mx);
            D[u].mn = min(D[u].mn, D[v].mn);
            return true;
        }
        return false;
    }
};
namespace subtask1{
    bool check(){
        return n <= 100 and q <= 100;
    }


    DSU timelineDSU[103];
    void solve(){
        FOR(i, 1, q){
            timelineDSU[i] = DSU(n + 1);
            FOR(j, 1, n){
                if (lamp[j] == '1') {
                    timelineDSU[i].unite(j, j + 1);
                }
            }

            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                lamp[u] = ((lamp[u] == '0') ? '1' : '0');
            }
            else{
                int ans = 0;
                FOR(j, 1, i){
                    if (timelineDSU[j].root(Query[i].l) == timelineDSU[j].root(Query[i].r)) {
                        ans++;
                    }
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask2{
    bool check(){
        FOR(i, 1, q){
            if (Query[i].type == "query" and Query[i].l != Query[i].r - 1) return false;
        }
        return true;
    }

    int pre[300003], lastTime[MAXN];
    void solve(){
        FOR(i, 1, n){
            pre[i] = 0;
            if (lamp[i] == '1') lastTime[i] = 1;
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '1') {
                    pre[u] += i - lastTime[u] + 1;
                    lastTime[u] = 0;
                    lamp[u] = '0';
                }
                else{
                    lastTime[u] = i + 1;
                    lamp[u] = '1';
                }
            }
            if (Query[i].type == "query"){
                int ans = pre[Query[i].l];
                if (lamp[Query[i].l] == '1'){
                    ans += i - lastTime[Query[i].l] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask3{
    char tmp[300005];
    bool check(){
        FOR(i, 1, n){
            tmp[i] = lamp[i];
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and tmp[Query[i].u] == '1') return false;
            if (Query[i].type == "toggle") tmp[Query[i].u] = '1';
        }
        return true;
    }

    /**
    Voi 2 dinh a va b, ta can tim thoi gian dau tien ma hai thang do ket hop lam 1. Cái này có thể giải bằng
    chặt nhị phân song song.

    Dùng reachability Tree.
    **/

    vector<int> reachability[MAXN * 2];
    int edgeTime[MAXN * 2];

    int P[22][MAXN * 2], depth[MAXN * 2];

    void dfs(int u, int p){
        P[0][u] = p;
        for(auto v: reachability[u]){
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]) u = P[i][u];
        }

        if (u == v) return u;

        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) {
                u = P[i][u];
                v = P[i][v];
            }
        }

        return P[0][u];
    }

    void solve(){
        int small_to_large = 0;
        int path_compression = 1;
        int roll_back = 0;
        DSU D(2 * n + 9, small_to_large, path_compression, roll_back);
        int cntEdge = n + 1;
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                ++cntEdge;
                edgeTime[cntEdge] = 1;

                int r1 = D.root(i);
                int r2 = D.root(i + 1);

                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;
                    reachability[cntEdge].pb(r2);
                }

            }

        }


        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                ++cntEdge;
                edgeTime[cntEdge] = i + 1;
                int r1 = D.root(u);
                int r2 = D.root(u + 1);
                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;

                    reachability[cntEdge].pb(r2);
                }
            }
        }

        FORD(i, 2 * n + 3, 1){
            if (P[0][i] == 0) dfs(i, -1);
        }

        FOR(i, 1, 20){
            FOR(j, 1, 2 * n + 3){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                P[i][j] = P[i - 1][P[i - 1][j]];
            }
        }

        FOR(i, 1, q){
            int ans = 0;
            if (Query[i].type == "query"){
                int l = Query[i].l;
                int r = Query[i].r;
                if (D.root(l) == D.root(r)){
                    int acs = lca(l, r);
                    if (i >= edgeTime[acs]) ans += i - edgeTime[acs] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

struct BinaryIndexedTree{
    vector<int> BIT;
    BinaryIndexedTree(int sz = 0){
        BIT.resize(sz + 9);
    }

    void update(int id, int val){
        for(int i = id; i < BIT.size(); i += i & (-i)){
            BIT[i] += val;
        }
    }

    int get(int id){
        int res = 0;
        for(int i = id; i > 0; i -= i & (-i)){
            res += BIT[i];
        }
        return res;
    }

    void updateRange(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }
};
namespace subtask4{
    bool check(){
        bool alreadyQuery = 0;
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and alreadyQuery) return false;
            if (Query[i].type == "query") alreadyQuery = true;
        }
        return true;
    }

    struct rectangle{
        int L, R, B, T, val;
        rectangle(int _L = 0, int _R = 0, int _B = 0, int _T = 0, int _v = 0){
            L = _L;
            R = _R;
            B = _B;
            T = _T;
            val = _v;
        }

    };

    vector<rectangle> rect;
    vector<iii> points;

    struct event{
        int x, type, l, r;
        event(int _x = 0, int _type = 0, int _l = 0, int _r = 0): x(_x), type(_type), l(_l), r(_r) {}
    };
    vector<int> valRectangleInclude(vector<rectangle> rect, vector<iii> points){
        vector<int> result(points.size());
        vector<event> events;
        BinaryIndexedTree BIT(300005);

        FOR(i, 0, (int) rect.size() - 1){
            events.pb(event(rect[i].L, rect[i].val, rect[i].B, rect[i].T));
            events.pb(event(rect[i].R + 1,-rect[i].val, rect[i].B, rect[i].T));
//            cerr << rect[i].L << ' ' << rect[i].R << ' ' << rect[i].B << ' ' << rect[i].T << ' ' << rect[i].val << endl;
        }

        FOR(i, 0, (int) points.size() - 1){
//            cerr << points[i].fi << ' ' << points[i].se.fi << ' ' << points[i].se.se << endl;
            events.pb(event(points[i].se.fi, 0, points[i].fi, points[i].se.se));
        }

        sort(events.begin(), events.end(), [&](const event &a, const event &b){
             return a.x < b.x;
        });

        for(int i = 0, j = 0; i < events.size(); i = j){
            j = i;
//            cerr << "X: " << events[i].x << endl;
            while(j < events.size() and events[j].x == events[i].x){
                if (events[j].type != 0) {
                    BIT.updateRange(events[j].l, events[j].r, events[j].type);
//                    cerr << "UPDATE: " << events[j].l << ' ' << events[j].r << ' ' << events[j].type << endl;
                }
                j++;
            }

            j = i;
            while(j < events.size() and events[j].x == events[i].x){
                 if (events[j].type == 0) {
//                    cerr << "GET: " << events[j].x << ' ' << events[j].r << endl;
                    result[events[j].l] = BIT.get(events[j].r);
                 }
                 j++;
            }
        }
        return result;
    }


    /**
    Moi lan ta them canh vao, ta chac no se tao 1 thanh phan lien thong moi, ta chi quan tam rang la
    2 doan ma no dang o thoi.
    Khi ta add 2 thang vao thi chac chan no se la hai thang tien de tao thanh 2 thang lon hon.
    **/

    vector<int> dsuRollback[MAXN << 2];
    DSU D;

    void addEvent(int nn, int l, int r, int u, int v, int e){
        if (l >= u and r <= v){
            dsuRollback[nn].pb(e);
            return;
        }
        if (l > v or r < u) return;
        int mid = (l + r) >> 1;
        addEvent(nn << 1, l, mid, u, v, e);
        addEvent(nn << 1 | 1, mid + 1, r, u, v, e);
    }

    void go(int nn, int l, int r){
        int sz = D.changes.size();
        for(auto p: dsuRollback[nn]){
            D.unite(p, p + 1);
            int rt = D.root(p);
            rect.pb(rectangle(D.D[rt].mn, p, p + 1, D.D[rt].mx, r - l + 1));
        }

        if (l != r){
            int mid = (l + r) >> 1;
            go(nn << 1, l, mid);
            go(nn << 1 | 1, mid + 1, r);
        }

        while(D.changes.size() > sz) D.rollback();


    }

    int lastTime[MAXN];
    void solve(){
        int startAsking = q + 1;
        FOR(i, 1, q){
            if (Query[i].type == "query") {
                startAsking = i;
                break;
            }
        }

        D = DSU(n + 1, 1, 0, 1);
        DSU current = DSU(n + 1, 1, 1, 0);

        FOR(i, 1, n){
            if (lamp[i] == '1') lastTime[i] = 1;
        }

        FOR(i, 1, startAsking - 1){
            int u = Query[i].u;
            if (lamp[u] == '1'){
                addEvent(1, 1, startAsking, lastTime[u], i, u);
                lastTime[u] = 0;
                lamp[u] = '0';
            }
            else{
                lamp[u] = '1';
                lastTime[u] = i + 1;
            }
        }

        FOR(i, 1, n){
            if (lastTime[i] > 0) addEvent(1, 1, startAsking, lastTime[i], startAsking, i);
        }

        go(1, 1, startAsking);

        FOR(i, 1, n){
            if (lamp[i] == '1') current.unite(i, i + 1);
        }


        FOR(i, startAsking, q){
            points.pb({i - startAsking, ii(Query[i].l, Query[i].r)});
        }

//        for(int i = 0; i < rect.size(); i++){
//            cerr << rect[i].val << endl;
//        }

        vector<int> result = valRectangleInclude(rect, points);

        FOR(i, startAsking, q){
            int l = Query[i].l;
            int r = Query[i].r;
            if (current.root(l) == current.root(r)){
                result[i - startAsking] += i - startAsking;
            }
            cout << result[i - startAsking] << endl;
        }


    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> q;
    FOR(i, 1, n){
        cin >> lamp[i];
    }
    FOR(i, 1, q){
        cin >> Query[i].type;
        if (Query[i].type == "toggle"){
            cin >> Query[i].u;

        }
        else if (Query[i].type == "query"){
            cin >> Query[i].l >> Query[i].r;
        }
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask4::check()) return subtask4::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

street_lamps.cpp: In constructor 'DSU::DSU(int, int, int, int)':
street_lamps.cpp:9:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DSU::DSUnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
   83 |         FOR(i, 0, D.size() - 1){
      |             ~~~~~~~~~~~~~~~~~~   
street_lamps.cpp:83:9: note: in expansion of macro 'FOR'
   83 |         FOR(i, 0, D.size() - 1){
      |         ^~~
street_lamps.cpp: In member function 'void BinaryIndexedTree::update(int, int)':
street_lamps.cpp:330:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  330 |         for(int i = id; i < BIT.size(); i += i & (-i)){
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'std::vector<int> subtask4::valRectangleInclude(std::vector<subtask4::rectangle>, std::vector<std::pair<int, std::pair<int, int> > >)':
street_lamps.cpp:397:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  397 |         for(int i = 0, j = 0; i < events.size(); i = j){
      |                               ~~^~~~~~~~~~~~~~~
street_lamps.cpp:400:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  400 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp:409:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  409 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void subtask4::go(int, int, int)':
street_lamps.cpp:455:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 6> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  455 |         while(D.changes.size() > sz) D.rollback();
      |               ~~~~~~~~~~~~~~~~~^~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:523:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  523 | main()
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:527:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  527 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:528:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  528 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 63312 KB Output is correct
2 Correct 13 ms 63300 KB Output is correct
3 Correct 12 ms 63556 KB Output is correct
4 Correct 12 ms 63568 KB Output is correct
5 Correct 13 ms 63608 KB Output is correct
6 Correct 12 ms 63580 KB Output is correct
7 Correct 13 ms 63568 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 64328 KB Output is correct
2 Correct 72 ms 64328 KB Output is correct
3 Correct 70 ms 64284 KB Output is correct
4 Correct 81 ms 64312 KB Output is correct
5 Correct 82 ms 64572 KB Output is correct
6 Correct 80 ms 64328 KB Output is correct
7 Correct 84 ms 64328 KB Output is correct
8 Correct 89 ms 65608 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 106576 KB Output is correct
2 Correct 16 ms 106692 KB Output is correct
3 Correct 17 ms 106452 KB Output is correct
4 Correct 18 ms 106744 KB Output is correct
5 Correct 166 ms 133696 KB Output is correct
6 Correct 268 ms 133812 KB Output is correct
7 Correct 333 ms 134216 KB Output is correct
8 Correct 543 ms 144616 KB Output is correct
9 Correct 92 ms 107336 KB Output is correct
10 Correct 104 ms 107336 KB Output is correct
11 Correct 104 ms 107592 KB Output is correct
12 Correct 118 ms 124224 KB Output is correct
13 Correct 563 ms 144704 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 64848 KB Output is correct
2 Correct 13 ms 64848 KB Output is correct
3 Correct 15 ms 64968 KB Output is correct
4 Correct 14 ms 65528 KB Output is correct
5 Correct 185 ms 117992 KB Output is correct
6 Correct 390 ms 178056 KB Output is correct
7 Correct 620 ms 260220 KB Output is correct
8 Correct 949 ms 374772 KB Output is correct
9 Correct 358 ms 168116 KB Output is correct
10 Correct 380 ms 168104 KB Output is correct
11 Correct 350 ms 168368 KB Output is correct
12 Correct 354 ms 168108 KB Output is correct
13 Correct 361 ms 168096 KB Output is correct
14 Correct 359 ms 168108 KB Output is correct
15 Correct 118 ms 130124 KB Output is correct
16 Correct 556 ms 150652 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 63312 KB Output is correct
2 Correct 13 ms 63300 KB Output is correct
3 Correct 12 ms 63556 KB Output is correct
4 Correct 12 ms 63568 KB Output is correct
5 Correct 13 ms 63608 KB Output is correct
6 Correct 12 ms 63580 KB Output is correct
7 Correct 13 ms 63568 KB Output is correct
8 Correct 66 ms 64328 KB Output is correct
9 Correct 72 ms 64328 KB Output is correct
10 Correct 70 ms 64284 KB Output is correct
11 Correct 81 ms 64312 KB Output is correct
12 Correct 82 ms 64572 KB Output is correct
13 Correct 80 ms 64328 KB Output is correct
14 Correct 84 ms 64328 KB Output is correct
15 Correct 89 ms 65608 KB Output is correct
16 Correct 16 ms 106576 KB Output is correct
17 Correct 16 ms 106692 KB Output is correct
18 Correct 17 ms 106452 KB Output is correct
19 Correct 18 ms 106744 KB Output is correct
20 Correct 166 ms 133696 KB Output is correct
21 Correct 268 ms 133812 KB Output is correct
22 Correct 333 ms 134216 KB Output is correct
23 Correct 543 ms 144616 KB Output is correct
24 Correct 92 ms 107336 KB Output is correct
25 Correct 104 ms 107336 KB Output is correct
26 Correct 104 ms 107592 KB Output is correct
27 Correct 118 ms 124224 KB Output is correct
28 Correct 563 ms 144704 KB Output is correct
29 Correct 12 ms 64848 KB Output is correct
30 Correct 13 ms 64848 KB Output is correct
31 Correct 15 ms 64968 KB Output is correct
32 Correct 14 ms 65528 KB Output is correct
33 Correct 185 ms 117992 KB Output is correct
34 Correct 390 ms 178056 KB Output is correct
35 Correct 620 ms 260220 KB Output is correct
36 Correct 949 ms 374772 KB Output is correct
37 Correct 358 ms 168116 KB Output is correct
38 Correct 380 ms 168104 KB Output is correct
39 Correct 350 ms 168368 KB Output is correct
40 Correct 354 ms 168108 KB Output is correct
41 Correct 361 ms 168096 KB Output is correct
42 Correct 359 ms 168108 KB Output is correct
43 Correct 118 ms 130124 KB Output is correct
44 Correct 556 ms 150652 KB Output is correct
45 Incorrect 32 ms 65168 KB Output isn't correct
46 Halted 0 ms 0 KB -