Submission #414402

#	Time	Username	Problem	Language	Result	Execution time	Memory
414402		usachevd0	Sweeping (JOI20_sweeping)	C++14	100 / 100	9673 ms	454532 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 INF32 = 1e9;
#ifdef LOCAL
const int maxN = 100, maxQ = 100;
#else
const int maxN = 1.5e6 + 6;
const int maxQ = 1e6 + 6;
#endif
int L;

struct pt {
    int x, y;
    
    pt(int _x = 0, int _y = 0): x(_x), y(_y) {}
    
    void read() {
        cin >> x >> y;
    }
} ans[maxQ], pos0[maxN];

namespace dsu {
    const int maxV = 2 * maxN;
    int q[maxV];
    int val[maxV];
    vector<int> vtx[maxV];
    
    void new_node(int x, int v) {
        q[x] = -1;
        val[x] = v;
        vtx[x] = {x};
    }
    int gt(int x) {
        return q[x] < 0 ? x : q[x] = gt(q[x]);
    }
    int gval(int x) {
        return val[gt(x)];
    }
    int join(int x, int y) {
        // debug(x, y);
        // debug(vtx[x]);
        // debug(vtx[y]);
        x = gt(x), y = gt(y);
        if (x == y) return x;
        if (-q[x] < -q[y]) swap(x, y);
        q[x] += q[y];
        q[y] = x;
        for (int i : vtx[y])
            vtx[x].push_back(i);
        vtx[y].clear();
        return x;
    }
}

bool here[2 * maxN];
void solve(int stx, int sty, vector<array<int, 3>> que) {
    if (que.empty()) return;
    int L1 = L - stx - sty;
    if (!L1) {
        for (auto q : que) {
            if (q[0] == 1) {
                ans[q[2]] = {stx, sty};
            }
        }
        return;
    }
    // debug(stx, sty);
    // for (auto q : que)
    //     cerr << q[0] << ' ' << q[1] << ' ' << q[2] << endl;
    int fnx = L - sty;
    int fny = L - stx;
    int midx = (stx + fnx) / 2;
    int midy = sty + L1 - (midx - stx);
    vector<array<int, 3>> que_up, que_ri;
    set<pii> px, py;
    for (auto q : que) {
        if (q[0] == 1) {
            int i = q[1];
            int t = q[2];
            if (here[i]) {
                ans[t].x = dsu::gval(i << 1);
                ans[t].y = dsu::gval(i << 1 | 1);
            } else if (pos0[i].x > midx) {
                que_ri.push_back(q);
            } else {
                que_up.push_back(q);
            }
        } else if (q[0] == 2) { // H
            int l = q[1];
            if (l >= midy - sty) {
                int x0 = stx + L1 - l;
                int comp = -1;
                while (!px.empty() && px.begin()->fi < x0) {
                    int c = px.begin()->se;
                    if (comp == -1)
                        comp = c;
                    else
                        comp = dsu::join(comp, c);
                    px.erase(px.begin());
                }
                if (comp != -1) {
                    dsu::val[comp] = x0;
                    px.insert({x0, comp});
                }
                
                if (l > midy - sty) {
                    q[1] -= (midy - sty + 1);
                    que_up.push_back(q);
                }
            } else {
                int x0 = stx + L1 - l;
                int y0 = sty + l;
                while (!py.empty() && py.begin()->fi <= y0) {
                    int c = py.begin()->se;
                    for (int ii : dsu::vtx[c]) {
                        int i = ii / 2;
                        if (!here[i]) continue;
                        here[i] = false;
                        pos0[i].x = x0;
                        pos0[i].y = dsu::val[c];
                        array<int, 3> temp;
                        temp[0] = 4, temp[1] = i;
                        que_ri.push_back(temp);
                    }
                    py.erase(py.begin());
                }
                
                que_ri.push_back(q);
            }
        } else if (q[0] == 3) { // V
            int l = q[1];
            if (l >= midx - stx) {
                int y0 = sty + L1 - l;
                int comp = -1;
                while (!py.empty() && py.begin()->fi < y0) {
                    int c = py.begin()->se;
                    if (comp == -1)
                        comp = c;
                    else
                        comp = dsu::join(comp, c);
                    py.erase(py.begin());
                }
                if (comp != -1) {
                    dsu::val[comp] = y0;
                    py.insert({y0, comp});
                }
                
                if (l > midx - stx) {
                    q[1] -= (midx - stx + 1);
                    que_ri.push_back(q);
                }
            } else {
                int y0 = sty + L1 - l;
                int x0 = stx + l;
                while (!px.empty() && px.begin()->fi <= x0) {
                    int c = px.begin()->se;
                    for (int ii : dsu::vtx[c]) {
                        int i = ii / 2;
                        if (!here[i]) continue;
                        here[i] = false;
                        pos0[i].y = y0;
                        pos0[i].x = dsu::val[c];
                        array<int, 3> temp;
                        temp[0] = 4, temp[1] = i;
                        que_up.push_back(temp);
                    }
                    px.erase(px.begin());
                }
                
                que_up.push_back(q);
            }
        } else {
            int i = q[1];
            int x = pos0[i].x, y = pos0[i].y;
            if (x <= midx && y <= midy) {
                // debug(i,x,y);
                here[i] = true;
                px.insert({x, i << 1});
                py.insert({y, i << 1 | 1});
                dsu::new_node(i << 1, x);
                dsu::new_node(i << 1 | 1, y);
            } else if (x > midx) {
                que_ri.push_back(q);
            } else {
                que_up.push_back(q);
            }
        }
    }
    solve(midx + 1, sty, que_ri);
    solve(stx, midy + 1, que_up);
}

int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, Q;
    cin >> L >> N >> Q;
    vector<array<int, 3>> que;
    for (int i = 1; i <= N; ++i) {
        pos0[i].read();
        array<int, 3> temp;
        temp[0] = 4, temp[1] = i;
        que.push_back(temp);
    }
    int cnt = 0;
    while (Q--) {
        array<int, 3> q;
        cin >> q[0];
        if (q[0] != 4) {
            cin >> q[1];
        } else {
            pos0[++N].read();
            q[1] = N;
        }
        if (q[0] == 1) {
            q[2] = cnt++;
        }
        que.push_back(q);
    }
    solve(0, 0, que);
    for (int i = 0; i < cnt; ++i)
        cout << ans[i].x << ' ' << ans[i].y << '\n';

    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: In function 'void solve(int, int, std::vector<std::array<int, 3> >)':
sweeping.cpp:125:9: warning: unused variable 'fny' [-Wunused-variable]
  125 |     int fny = L - stx;
      |         ^~~

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