oj.uz

답안 #213160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213160 2020-03-25T05:50:02 Z qkxwsm 청소 (JOI20_sweeping) C++14
64 / 100
 4170 ms 128340 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

mt19937 rng(69);
template<class T>
T randomize(T mod)
{
    return uniform_int_distribution<T>(0, mod - 1)(rng);
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 530013;
const int INF = 1000000007;

int N, M, Q;

int indexof(int v, vi &vec)
{
    return UB(ALL(vec), v) - vec.begin() - 1;
}

bool cmp(pii a, pii b)
{
    return MP(a.fi, -a.se) > MP(b.fi, -b.se);
}

struct node
{
    node *ch[2], *p;
    pii pos, lazy;
    int pri;
    node(int x, int y)
    {
        ch[0] = nullptr;
        ch[1] = nullptr;
        p = nullptr;
        pos = {x, y};
        lazy = {-1, -1};
        pri = randomize(INF);
    }
};

void push(node *t)
{
    if (!t) return;
    if (t -> lazy == MP(-1, -1)) return;
    ckmax(t -> pos.fi, t -> lazy.fi);
    ckmax(t -> pos.se, t -> lazy.se);
    if (t -> ch[0])
    {
        ckmax(t -> ch[0] -> lazy.fi, t -> lazy.fi);
        ckmax(t -> ch[0] -> lazy.se, t -> lazy.se);
        assert(t -> ch[0] -> p == t);
    }
    if (t -> ch[1])
    {
        ckmax(t -> ch[1] -> lazy.fi, t -> lazy.fi);
        ckmax(t -> ch[1] -> lazy.se, t -> lazy.se);
        assert(t -> ch[1] -> p == t);
    }
    t -> lazy = {-1, -1};
    return;
}
typedef pair<node*, node*> pnn;
pnn split(node* t, int v, bool dir)
{
    //v goes to the right tho...
    if (!t) return {nullptr, nullptr};
    push(t);
    if ((!dir && t -> pos.fi > v) || (dir && t -> pos.se < v))
    {
        pnn p = split(t -> ch[0], v, dir);
        t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
        if (p.fi) p.fi -> p = nullptr;
        return {p.fi, t};
    }
    else
    {
        pnn p = split(t -> ch[1], v, dir);
        t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
        if (p.se) p.se -> p = nullptr;
        return {t, p.se};
    }
}
pnn Split(node *t, pii v)
{
    if (!t) return {nullptr, nullptr};
    push(t);
    if (cmp(t -> pos, v))
    {
        pnn p = Split(t -> ch[0], v);
        t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
        if (p.fi) p.fi -> p = nullptr;
        return {p.fi, t};
    }
    else
    {
        pnn p = Split(t -> ch[1], v);
        t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
        if (p.se) p.se -> p = nullptr;
        return {t, p.se};
    }
}
node *merge(node *l, node *r)
{
    push(l); push(r);
    if (!l) return r;
    if (!r) return l;
    // assert(l != r);
    if (l -> pri > r -> pri)
    {
        l -> ch[1] = merge(l -> ch[1], r); if (l -> ch[1]) l -> ch[1] -> p = l;
        return l;
    }
    else
    {
        r -> ch[0] = merge(l, r -> ch[0]); if (r -> ch[0]) r -> ch[0] -> p = r;
        return r;
    }
}
void get(node *t)
{
    vector<node*> vn;
    while(t)
    {
        vn.PB(t);
        t = t -> p;
    }
    reverse(ALL(vn));
    for (auto w : vn)
    {
        push(w);
    }
}
void inorder(node *t)
{
    if (!t) return;
    push(t);
    inorder(t -> ch[0]);
    cerr << t -> pos.fi << ',' << t -> pos.se << ',' << t -> pri << ' ';
    inorder(t -> ch[1]);
}

node *root;
node *V[MAXN];

void ins(int x, int y, int idx)
{
    // inorder(root); cerr << endl;
    // cerr << "insert " << x << ' ' << y << endl;
    V[idx] = new node(x, y);
    pnn p = Split(root, {x, y});
    // cerr << "ok" << endl;
    root = merge(p.fi, merge(V[idx], p.se));
}

struct segtree
{
    int seg[2 * MAXN];
    priority_queue<pii, vector<pii>, greater<pii> > pts[MAXN];
    vi res;
    void build(int w, int L, int R)
    {
        if (L == R)
        {
            seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
            return;
        }
        int mid = (L + R) >> 1;
        build(w << 1, L, mid);
        build(w << 1 | 1, mid + 1, R);
        seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
    }
    void walk(int w, int L, int R, int a, int b, int v)
    {
        if (b < L || R < a || seg[w] > v) return;
        if (L == R)
        {
            while(!pts[L].empty() && pts[L].top().fi <= v)
            {
                res.PB(pts[L].top().se);
                pts[L].pop();
            }
            seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
            return;
        }
        int mid = (L + R) >> 1;
        walk(w << 1, L, mid, a, b, v);
        walk(w << 1 | 1, mid + 1, R, a, b, v);
        seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
        return;
    }
    int query(int w, int L, int R, int a, int b)
    {
        if (a <= L && R <= b) return seg[w];
        int mid = (L + R) >> 1;
        if (b <= mid) return query(w << 1, L, mid, a, b);
        if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
        return min(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
    }
};

segtree segx, segy;
vi cx, cy;
pii arr[MAXN];

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M >> Q;
    FOR(i, 0, M)
    {
        pii p;
        cin >> p.fi >> p.se;
        cx.PB(p.fi);
        cy.PB(p.se);
        arr[i] = p;
    }
    sort(ALL(cx)); cx.erase(unique(ALL(cx)), cx.end());
    sort(ALL(cy)); cy.erase(unique(ALL(cy)), cy.end());
    FOR(i, 0, M)
    {
        int x = indexof(arr[i].fi, cx), y = indexof(arr[i].se, cy);
        segx.pts[x].push({arr[i].se, i});
        segy.pts[y].push({arr[i].fi, i});
    }
    segx.build(1, 0, SZ(cx) - 1);
    segy.build(1, 0, SZ(cy) - 1);
    while(Q--)
    {
        // cerr << "TREE\n";
        int typ, idx;
        cin >> typ >> idx;
        // cerr << "QUERY " << typ << ' ' << idx << endl;
        if (typ == 1)
        {
            idx--;
            if (idx >= M) continue;
            // cerr << "idx = " << idx << endl;
            if (arr[idx] == MP(-1, -1))
            {
                get(V[idx]);
                pii p = V[idx] -> pos;
                cout << p.fi << ' ' << p.se << '\n';
            }
            else
            {
                cout << arr[idx].fi << ' ' << arr[idx].se << '\n';
            }
        }
        if (typ == 2)
        {
            //horizontal sweep.
            // cerr << "horizontal " << idx << endl;
            pnn p = split(root, idx + 1, true), p1 = split(p.se, N - idx + 1, false);
            // // inorder(p1.fi);
            if (p1.fi)
            {
                p1.fi -> lazy.fi = N - idx;
            }
            root = merge(p.fi, merge(p1.fi, p1.se));
            segy.walk(1, 0, SZ(cy) - 1, 0, indexof(idx, cy), N - idx);
            vi vec = segy.res; segy.res.clear();
            for (int x : vec)
            {
                if (arr[x] == MP(-1, -1)) continue;
                ins(N - idx, arr[x].se, x);
                arr[x] = MP(-1, -1);
            }
            // assert(segy.query(1, 0, SZ(cy) - 1, 0, indexof(idx, cy)) >= N - idx);
            //push shit horizontally.
            //everything with x <= N-idx and y <= idx gets pushed to x=N-idx.
        }
        if (typ == 3)
        {
            pnn p = split(root, N - idx + 1, true), p1 = split(p.se, idx, false);
            if (p1.fi)
            {
                p1.fi -> lazy.se = N - idx;
            }
            //push shit vertically
            //everything with x <= idx && y <= N-idx gets pushed to y = N-idx.
            root = merge(p.fi, merge(p1.fi, p1.se));
            segx.walk(1, 0, SZ(cx) - 1, 0, indexof(idx, cx), N - idx);
            vi vec = segx.res; segx.res.clear();
            for (int x : vec)
            {
                if (arr[x] == MP(-1, -1)) continue;
                ins(arr[x].fi, N - idx, x);
                arr[x] = MP(-1, -1);
            }
            // assert(segx.query(1, 0, SZ(cx) - 1, 0, indexof(idx, cx)) >= N - idx);
        }
        if (typ == 4)
        {
            cin >> idx;
            continue;
        }
    }
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 33920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2917 ms 114008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2390 ms 126424 KB Output is correct
2 Correct 2516 ms 126292 KB Output is correct
3 Correct 2183 ms 125528 KB Output is correct
4 Correct 2316 ms 126040 KB Output is correct
5 Correct 2430 ms 128340 KB Output is correct
6 Correct 2380 ms 126288 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2390 ms 126424 KB Output is correct
2 Correct 2516 ms 126292 KB Output is correct
3 Correct 2183 ms 125528 KB Output is correct
4 Correct 2316 ms 126040 KB Output is correct
5 Correct 2430 ms 128340 KB Output is correct
6 Correct 2380 ms 126288 KB Output is correct
7 Correct 3409 ms 116432 KB Output is correct
8 Correct 3528 ms 116572 KB Output is correct
9 Correct 3361 ms 116440 KB Output is correct
10 Correct 2702 ms 125648 KB Output is correct
11 Correct 4170 ms 126036 KB Output is correct
12 Correct 3080 ms 127704 KB Output is correct
13 Correct 3112 ms 127696 KB Output is correct
14 Correct 203 ms 33536 KB Output is correct
15 Correct 940 ms 69584 KB Output is correct
16 Correct 3368 ms 115796 KB Output is correct
17 Correct 3283 ms 115672 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 33920 KB Output isn't correct
2 Halted 0 ms 0 KB -