oj.uz

답안 #213159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213159 2020-03-25T05:48:24 Z qkxwsm 청소 (JOI20_sweeping) C++14
64 / 100
 4048 ms 176848 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 = 1000013;
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 42 ms 63232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2433 ms 155860 KB Output is correct
2 Correct 2504 ms 155864 KB Output is correct
3 Correct 2287 ms 154960 KB Output is correct
4 Correct 2317 ms 155480 KB Output is correct
5 Correct 2407 ms 157784 KB Output is correct
6 Correct 2444 ms 155736 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2433 ms 155860 KB Output is correct
2 Correct 2504 ms 155864 KB Output is correct
3 Correct 2287 ms 154960 KB Output is correct
4 Correct 2317 ms 155480 KB Output is correct
5 Correct 2407 ms 157784 KB Output is correct
6 Correct 2444 ms 155736 KB Output is correct
7 Correct 3522 ms 145872 KB Output is correct
8 Correct 3524 ms 165712 KB Output is correct
9 Correct 3370 ms 165584 KB Output is correct
10 Correct 2759 ms 174164 KB Output is correct
11 Correct 4048 ms 175060 KB Output is correct
12 Correct 3042 ms 176848 KB Output is correct
13 Correct 3148 ms 176724 KB Output is correct
14 Correct 212 ms 66936 KB Output is correct
15 Correct 998 ms 113112 KB Output is correct
16 Correct 3398 ms 164952 KB Output is correct
17 Correct 3292 ms 165080 KB Output is correct

Subtask #5
0 / 25.0

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