Submission #414294

#	Time	Username	Problem	Language	Result	Execution time	Memory
414294		usachevd0	Sweeping (JOI20_sweeping)	C++17	12 / 100	18090 ms	25824 KiB

sweeping

#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc optimize("fast-math")
#pragma gcc target("avx,avx2,fma,sse,sse2,sse3,sse4,sse4.1,popcnt")
#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 = 1111;
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 bgY[K];
int f[K][K][2];

void rec() {
    // cerr << "rec" << endl;
    // for (int i = 1; i <= N; ++i) if (spawnT[i] == 0) debug(i, P[i][0], P[i][1]);
    // 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];
    // }
    
    fill(bgY, bgY + X[0], 0);
    memset(f, 0, sizeof f);
    for (int t = 0; t < sz; ++t) {
        int ql = buf[t].l;
        int qd = buf[t].d;
        
        if (qd == 0) { // V
            for (int i = 0; i < X[0] && rx[0][i] <= ql; ++i) {
                for (; bgY[i] < X[1] && rx[1][bgY[i]] < L - ql; ++bgY[i]) {
                    f[i][bgY[i]][1] = 1;
                }
                if (bgY[i] < X[1] && rx[1][bgY[i]] == L - ql) 
                    f[i][bgY[i]][1] = 2;
            }
        } else { // H
            for (int i = 0; i < X[0] && rx[0][i] <= L - ql; ++i) {
                if (rx[0][i] == L - ql) {
                    for (int j = bgY[i]; j < X[1] && rx[1][j] <= ql; ++j) {
                        f[i][j][0] = 2;
                    }
                    break;
                }
                for (; bgY[i] < X[1] && rx[1][bgY[i]] <= ql; ++bgY[i]) {
                    f[i][bgY[i]][0] = 1;
                }
            }
        }
    }
    for (int i = X[0] - 1; i >= 0; --i)
        for (int j = X[1] - 1; j >= 0; --j) {
            // debug(i, j, f[i][j][0], f[i][j][1]);
            if (f[i][j][1] == 1) {
                f[i][j][0] = f[i][j + 1][0];
                f[i][j][1] = f[i][j + 1][1];
                if (f[i][j][1] == -1)
                    f[i][j][1] = rx[1][j + 1];
            } else if (f[i][j][0] == 1) {
                f[i][j][0] = f[i + 1][j][0];
                f[i][j][1] = f[i + 1][j][1];
                if (f[i][j][0] == -1)
                    f[i][j][0] = rx[0][i + 1];
            } else {
                f[i][j][0] = (f[i][j][0] == 0 ? -1 : rx[0][i]);
                f[i][j][1] = (f[i][j][1] == 0 ? -1 : rx[1][j]);
            }
            // debug(i, j, f[i][j][0], f[i][j][1]);
        }
    
    
    for (int i = 1; i <= N; ++i) {
        if (spawnT[i] != 0) {
            for (int t = spawnT[i]; t < sz; ++t) {
                auto& q = buf[t];
                if (P[i][q.d] <= q.l)
                    chkmax(P[i][q.d ^ 1], L - q.l);
            }
            spawnT[i] = 0;
            continue;
        }
        int c0 = lower_bound(rx[0], rx[0] + X[0], P[i][0]) - rx[0];
        int c1 = lower_bound(rx[1], rx[1] + X[1], P[i][1]) - rx[1];
        // debug(i, c[0], c[1]);
        if (c0 < X[0] && c1 < X[1] && rx[0][c0] + rx[1][c1] <= L) {
            if (f[c0][c1][0] != -1)
                P[i][0] = f[c0][c1][0];
            if (f[c0][c1][1] != -1)
                P[i][1] = f[c0][c1][1];
        }
        
        // debug(i, P[i][0], P[i][1]);
        spawnT[i] = 0;
    }
    // for (int i = 1; i <= N; ++i)
    //     debug(i, P[i][0], P[i][1]);
    sz = 0;
}


int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    /*L = 1e9;
    N = 5e5;
    Q = 1e6;
    auto f = [&](ll K) -> ll {
        return Q * K + (Q / K + 1) * (K * K * 2 + (N + Q) * (log2(K) + 1));
    };
    ll mn = 1e18;
    int minK = -1;
    for (int K = 1; K <= Q; ++K) {
        if (chkmin(mn, f(K)))
            minK = K;
    }
    debug(minK, mn / 1e8);
    exit(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) {
                int qd = buf[t].d;
                int ql = buf[t].l;
                if (p[qd] <= ql)
                    chkmax(p[qd ^ 1], L - ql);
            }
            #ifdef LOCAL
                if (N > 20) continue;
            #endif
            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();
        }
    }
    debug(Time);

    return 0;
}

Compilation message (stderr)

sweeping.cpp:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
sweeping.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
sweeping.cpp:3: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    3 | #pragma gcc optimize("fast-math")
      | 
sweeping.cpp:4: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
    4 | #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,sse4,sse4.1,popcnt")
      | 
sweeping.cpp:196:13: warning: "/*" within comment [-Wcomment]
  196 |     exit(0);/**/
      |              
sweeping.cpp: In function 'int32_t main()':
sweeping.cpp:44:24: warning: statement has no effect [-Wunused-value]
   44 |     #define debug(...) 1337
      |                        ^~~~
sweeping.cpp:237:5: note: in expansion of macro 'debug'
  237 |     debug(Time);
      |     ^~~~~

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