Submission #414179

#	Time	Username	Problem	Language	Result	Execution time	Memory
414179		usachevd0	Sweeping (JOI20_sweeping)	C++14	1 / 100	18094 ms	7188 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int maxN = 1.5e6 + 6;
const int maxQ = 1e6 + 6;
const int K = 2;
int L, N, Q;

int P[maxN][2];
int spawnT[maxN];

struct Query {
    int d, l;
} buf[K + 3];
int sz;

int rx[2][K], X[2];

int newCoord[K];
int f[K + 1][K][K][2];

void rec() {
    // cerr << "rec" << endl;
    // for (int t = 0; t < sz; ++t) {
    //     auto& q = buf[t];
    //     cerr << (q.d == 0 ? 'V' : 'H') << ' ' << q.l << endl;
    // }
    X[0] = X[1] = 0;
    for (int t = 0; t < sz; ++t) {
        auto& q = buf[t];
        rx[q.d][X[q.d]++] = q.l;
        rx[q.d ^ 1][X[q.d ^ 1]++] = L - q.l;
    }
    for (int a = 0; a < 2; ++a) {
        sort(rx[a], rx[a] + X[a]);
        X[a] = unique(rx[a], rx[a] + X[a]) - rx[a];
        // debug(a);
        // mdebug(rx[a], X[a]);
    }
    for (int t = 0; t < sz; ++t) {
        auto& q = buf[t];
        newCoord[t] = lower_bound(rx[q.d ^ 1], rx[q.d ^ 1] + X[q.d ^ 1], L - q.l) - rx[q.d ^ 1];
    }
    
    for (int i = 0; i < X[0]; ++i)
        for (int j = 0; j < X[1] && rx[0][i] + rx[1][j] <= L; ++j)
            f[sz][i][j][0] = f[sz][i][j][1] = -1;
    int p[2];
    for (int t = sz - 1; t >= 0; --t) {
        auto& q = buf[t];
        int nc = newCoord[t];
        for (int i = 0; i < X[0]; ++i) {
            p[0] = rx[0][i];
            for (int j = 0; j < X[1] && p[0] + rx[1][j] <= L; ++j) {
                p[1] = rx[1][j];
                if (p[q.d] <= q.l && p[q.d ^ 1] <= L - q.l) {
                    if (!q.d) {
                        f[t][i][j][0] = f[t + 1][i][nc][0];
                        f[t][i][j][1] = f[t + 1][i][nc][1];
                        if (f[t][i][j][1] == -1) {
                            f[t][i][j][1] = L - q.l;
                        }
                    } else {
                        f[t][i][j][0] = f[t + 1][nc][j][0];
                        f[t][i][j][1] = f[t + 1][nc][j][1];
                        if (f[t][i][j][0] == -1) {
                            f[t][i][j][0] = L - q.l;
                        }
                    }
                } else {
                    f[t][i][j][0] = f[t + 1][i][j][0];
                    f[t][i][j][1] = f[t + 1][i][j][1];
                }
            }
        } 
    }
    for (int i = 1; i <= N; ++i) {
        int c[2];
        for (int a = 0; a < 2; ++a) {
            c[a] = lower_bound(rx[a], rx[a] + X[a], P[i][a]) - rx[a];
        }
        // debug(i, c[0], c[1]);
        if (c[0] < X[0] && c[1] < X[1] && rx[0][c[0]] + rx[1][c[1]] <= L) {
            int t = spawnT[i];
            for (int a = 0; a < 2; ++a) {
                if (f[t][c[0]][c[1]][a] != -1) {
                    P[i][a] = f[t][c[0]][c[1]][a];
                }
            }
        }
        
        // debug(i, P[i][0], P[i][1]);
        spawnT[i] = 0;
    }
    sz = 0;
}


int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> L >> N >> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> P[i][0] >> P[i][1];
    }
    sz = 0;
    while (Q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int i;
            cin >> i;
            int p[2] = {P[i][0], P[i][1]};
            for (int t = spawnT[i]; t < sz; ++t) {
                auto& q = buf[t];
                if (p[q.d] <= q.l)
                    chkmax(p[q.d ^ 1], L - q.l);
            }
            cout << p[0] << ' ' << p[1] << '\n';
        } else if (tp == 2) {
            int l;
            cin >> l;
            buf[sz++] = {1, l};
        } else if (tp == 3) {
            int l;
            cin >> l;
            buf[sz++] = {0, l};
        } else {
            ++N;
            spawnT[N] = sz;
            cin >> P[N][0] >> P[N][1];
        }
        if (sz >= K) {
            rec();
        }
    }

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25