oj.uz

Submission #414402

# Submission time Handle Problem Language Result Execution time Memory
414402 2021-05-30T11:57:57 Z usachevd0 Sweeping (JOI20_sweeping) C++14
100 / 100
 9673 ms 454532 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 91204 KB Output is correct
2 Correct 58 ms 90820 KB Output is correct
3 Correct 54 ms 91176 KB Output is correct
4 Correct 71 ms 91152 KB Output is correct
5 Correct 70 ms 91328 KB Output is correct
6 Correct 54 ms 91000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3696 ms 243412 KB Output is correct
2 Correct 3547 ms 241252 KB Output is correct
3 Correct 3539 ms 240068 KB Output is correct
4 Correct 4174 ms 286184 KB Output is correct
5 Correct 8740 ms 250380 KB Output is correct
6 Correct 7159 ms 273912 KB Output is correct
7 Correct 3710 ms 240268 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4836 ms 249748 KB Output is correct
2 Correct 5045 ms 253048 KB Output is correct
3 Correct 2880 ms 282384 KB Output is correct
4 Correct 5375 ms 368872 KB Output is correct
5 Correct 5803 ms 318800 KB Output is correct
6 Correct 3747 ms 255160 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4836 ms 249748 KB Output is correct
2 Correct 5045 ms 253048 KB Output is correct
3 Correct 2880 ms 282384 KB Output is correct
4 Correct 5375 ms 368872 KB Output is correct
5 Correct 5803 ms 318800 KB Output is correct
6 Correct 3747 ms 255160 KB Output is correct
7 Correct 3850 ms 232912 KB Output is correct
8 Correct 3782 ms 245756 KB Output is correct
9 Correct 3994 ms 234320 KB Output is correct
10 Correct 4131 ms 273292 KB Output is correct
11 Correct 6367 ms 320492 KB Output is correct
12 Correct 9673 ms 287716 KB Output is correct
13 Correct 7747 ms 386112 KB Output is correct
14 Correct 229 ms 125844 KB Output is correct
15 Correct 1619 ms 231564 KB Output is correct
16 Correct 3506 ms 260808 KB Output is correct
17 Correct 3845 ms 265484 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 91204 KB Output is correct
2 Correct 58 ms 90820 KB Output is correct
3 Correct 54 ms 91176 KB Output is correct
4 Correct 71 ms 91152 KB Output is correct
5 Correct 70 ms 91328 KB Output is correct
6 Correct 54 ms 91000 KB Output is correct
7 Correct 3696 ms 243412 KB Output is correct
8 Correct 3547 ms 241252 KB Output is correct
9 Correct 3539 ms 240068 KB Output is correct
10 Correct 4174 ms 286184 KB Output is correct
11 Correct 8740 ms 250380 KB Output is correct
12 Correct 7159 ms 273912 KB Output is correct
13 Correct 3710 ms 240268 KB Output is correct
14 Correct 4836 ms 249748 KB Output is correct
15 Correct 5045 ms 253048 KB Output is correct
16 Correct 2880 ms 282384 KB Output is correct
17 Correct 5375 ms 368872 KB Output is correct
18 Correct 5803 ms 318800 KB Output is correct
19 Correct 3747 ms 255160 KB Output is correct
20 Correct 3850 ms 232912 KB Output is correct
21 Correct 3782 ms 245756 KB Output is correct
22 Correct 3994 ms 234320 KB Output is correct
23 Correct 4131 ms 273292 KB Output is correct
24 Correct 6367 ms 320492 KB Output is correct
25 Correct 9673 ms 287716 KB Output is correct
26 Correct 7747 ms 386112 KB Output is correct
27 Correct 229 ms 125844 KB Output is correct
28 Correct 1619 ms 231564 KB Output is correct
29 Correct 3506 ms 260808 KB Output is correct
30 Correct 3845 ms 265484 KB Output is correct
31 Correct 3349 ms 288132 KB Output is correct
32 Correct 4116 ms 275668 KB Output is correct
33 Correct 3106 ms 249660 KB Output is correct
34 Correct 4189 ms 277364 KB Output is correct
35 Correct 4294 ms 279952 KB Output is correct
36 Correct 4075 ms 302280 KB Output is correct
37 Correct 7940 ms 419972 KB Output is correct
38 Correct 7954 ms 454532 KB Output is correct
39 Correct 7499 ms 368392 KB Output is correct
40 Correct 3619 ms 270660 KB Output is correct