oj.uz

Submission #891274

# Submission time Handle Problem Language Result Execution time Memory
891274 2023-12-22T15:59:11 Z vjudge1 Seats (IOI18_seats) C++17
0 / 100
 4000 ms 94540 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct AINT {
    int n;
    vi mi, ma;
    AINT(int N = 0) : n(N), mi(4 * N), ma(4 * N) {} 
    void init(int N) {
        n = N;
        mi.assign(4 * N, 0);
        ma.assign(4 * N, 0);
    }
    void update(int p, int v) { update(p, v, 1, 0, n - 1); }
    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
            mi[u] = ma[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        mi[u] = min(mi[u << 1], mi[u << 1 | 1]);
        ma[u] = max(ma[u << 1], ma[u << 1 | 1]);
    }

    ii query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    ii query(int l, int r, int u, int s, int d) {
        if( d < l || r < s ) return {1e9, 0};
        if(l <= s && d <= r)
            return make_pair(mi[u], ma[u]);
        auto [mi1, ma1] = query(l, r, u << 1, s, (s + d) >> 1);
        auto [mi2, ma2] = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        return make_pair(min(mi1, mi2), max(ma1, ma2));
    }
};

vi r, c;

int reg = 0;

int tip = 0;

AINT AR, AC;

int h, w;

void give_initial_chart(int H, int W, vi R, vi C) {
    h = H;
    w = W;

    r = R;
    c = C;
    AR.init(H * W);
    AC.init(H * W);
    for(int i = 0; i < H * W; ++i) {
        AR.update(i, R[i]);
        AC.update(i, C[i]);
    }
}

bool ok(int l, int c) {
    auto [mir, mar] = AR.query(0, l * c - 1); 
    auto [mic, mac] = AC.query(0, l * c - 1);
    return (l * c) == ((mar - mir + 1) * (mac - mic + 1));
}

int swap_seats(int a, int b) {
    swap(r[a], r[b]);
    swap(c[a], c[b]);

    AR.update(a, r[a]);
    AR.update(b, r[b]);
    AC.update(a, c[a]);
    AC.update(b, c[b]);

    int hc = 1, wc = 1, re = 1;

    while(hc < h || wc < w) {
        int facut = 0;
        for(int delta = 1;; ++delta) {
            int hh = hc + delta;
            int ww = wc + delta;
            if(hh > h && ww > w) break;
            if(hh <= h && ok(hh, wc)) {
                hc = hh;
                ++re;
                facut = 1;
                break;
            }
            if(ww <= w && ok(hc, ww)) {
                wc = ww;
                ++re;
                facut = 1;
                break;
            }
        }
        if(!facut) {
            if(hc < h)
                ++hc;
            else
                ++wc;
        }
    }

    return re;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Incorrect 5 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Incorrect 5 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4081 ms 94540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4074 ms 1368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1988 KB Output is correct
2 Correct 24 ms 1752 KB Output is correct
3 Correct 249 ms 1908 KB Output is correct
4 Execution timed out 4075 ms 2100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Incorrect 5 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -