Submission #414237

# Submission time Handle Problem Language Result Execution time Memory
414237 2021-05-30T09:32:18 Z usachevd0 Sweeping (JOI20_sweeping) C++17
12 / 100
18000 ms 102412 KB
#include <bits/stdc++.h>
#pragma gcc optimize

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 = 3300;
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 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];
    // }
    
    // 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];
    //             }
    //         }
    //     } 
    // }
    fill(bgY, bgY + X[0], 0);
    memset(f, 0, sizeof f);
    for (int t = 0; t < sz; ++t) {
        auto& q = buf[t];
        
        if (q.d == 0) { // V
            for (int i = 0; i < X[0] && rx[0][i] <= q.l; ++i) {
                for (; bgY[i] < X[1] && rx[1][bgY[i]] < L - q.l; ++bgY[i]) {
                    f[i][bgY[i]][1] = 1;
                }
                if (bgY[i] < X[1] && rx[1][bgY[i]] == L - q.l) 
                    f[i][bgY[i]][1] = 2;
            }
        } else { // H
            for (int i = 0; i < X[0] && rx[0][i] <= L - q.l; ++i) {
                if (rx[0][i] == L - q.l) {
                    for (int j = bgY[i]; j < X[1] && rx[1][j] <= q.l; ++j) {
                        f[i][j][0] = 2;
                    }
                    break;
                }
                for (; bgY[i] < X[1] && rx[1][bgY[i]] <= q.l; ++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 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) {
            for (int a = 0; a < 2; ++a) {
                if (f[c[0]][c[1]][a] != -1) {
                    P[i][a] = f[c[0]][c[1]][a];
                }
            }
        }
        
        // 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) {
                auto& q = buf[t];
                if (p[q.d] <= q.l)
                    chkmax(p[q.d ^ 1], L - q.l);
            }
            #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

sweeping.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize
      | 
sweeping.cpp:228:13: warning: "/*" within comment [-Wcomment]
  228 |     exit(0);/**/
      |              
sweeping.cpp: In function 'int32_t main()':
sweeping.cpp:41:24: warning: statement has no effect [-Wunused-value]
   41 |     #define debug(...) 1337
      |                        ^~~~
sweeping.cpp:268:5: note: in expansion of macro 'debug'
  268 |     debug(Time);
      |     ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 8 ms 436 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 12 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 18024 ms 102412 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 15307 ms 101548 KB Output is correct
2 Correct 16640 ms 101380 KB Output is correct
3 Correct 16622 ms 100928 KB Output is correct
4 Correct 15964 ms 101384 KB Output is correct
5 Correct 16236 ms 101372 KB Output is correct
6 Correct 16743 ms 101628 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 15307 ms 101548 KB Output is correct
2 Correct 16640 ms 101380 KB Output is correct
3 Correct 16622 ms 100928 KB Output is correct
4 Correct 15964 ms 101384 KB Output is correct
5 Correct 16236 ms 101372 KB Output is correct
6 Correct 16743 ms 101628 KB Output is correct
7 Execution timed out 18090 ms 98448 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 8 ms 436 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 12 ms 332 KB Output is correct
7 Execution timed out 18024 ms 102412 KB Time limit exceeded
8 Halted 0 ms 0 KB -