oj.uz

Submission #616975

# Submission time Handle Problem Language Result Execution time Memory
616975 2022-08-01T08:02:09 Z 박상훈(#8502) Sweeping (JOI20_sweeping) C++17
10 / 100
 2771 ms 75312 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
namespace I{
    vector<int> X, Y, T, A, B;
}

struct Seg{
    int tree[4400400], lazy[4400400];
    void propagate(int i, int l, int r){
        tree[i] = max(tree[i], lazy[i]);
        if (l!=r){
            lazy[i<<1] = max(lazy[i<<1], lazy[i]);
            lazy[i<<1|1] = max(lazy[i<<1|1], lazy[i]);
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x, bool flag = 0){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            if (flag) {tree[i] = x; return;}
            lazy[i] = x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x, flag); update(i<<1|1, m+1, r, s, e, x, flag);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    int query(int i, int l, int r, int s){
        propagate(i, l, r);
        if (r<s || s<l) return 0;
        if (l==r) return tree[i];
        int m = (l+r)>>1;
        return max(query(i<<1, l, m, s), query(i<<1|1, m+1, r, s));
    }
    int left_bound(int i, int l, int r, int x){
        propagate(i, l, r);
        if (tree[i] <= x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int ret = left_bound(i<<1, l, m, x);
        if (ret!=-1) return ret;
        return left_bound(i<<1|1, m+1, r, x);
    }
    int right_bound(int i, int l, int r, int x){
        propagate(i, l, r);
        if (tree[i] <= x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int ret = right_bound(i<<1|1, m+1, r, x);
        if (ret!=-1) return ret;
        return right_bound(i<<1, l, m, x);
    }
}treex, treey;

struct Node{
    int x, y, i;
    Node(){}
    Node(int _x, int _y, int _i): x(_x), y(_y), i(_i) {}
    bool operator < (const Node &N) const{
        return tie(y, x, i) < tie(N.y, N.x, N.i);
    }
};

int n, q, pos[2002000];

vector<int> X, Y;
void compress(vector<int> &X){sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());}
int getidx(const vector<int> &a, int x) {return lower_bound(a.begin(), a.end(), x) - a.begin();}

void input(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    X.push_back(-2e9);
    X.push_back(2e9);
    Y.push_back(-2e9);
    Y.push_back(2e9);

    int d;
    cin >> d >> n >> q;
    I::X.resize(n+1);
    I::Y.resize(n+1);
    I::T.resize(q+1);
    I::A.resize(q+1);
    I::B.resize(q+1);

    vector<Node> tmp;

    for (int i=1;i<=n;i++){
        cin >> I::X[i] >> I::Y[i];
        X.push_back(I::X[i]);
        Y.push_back(I::Y[i]);

        tmp.emplace_back(I::X[i], I::Y[i], i);
    }

    for (int i=1;i<=q;i++){
        cin >> I::T[i] >> I::A[i];
        if (I::T[i]==4){
            cin >> I::B[i];
            ++n;
            tmp.emplace_back(I::A[i], I::B[i], n);
        }
        else if (I::T[i]==2){
            I::B[i] = I::A[i];
            I::A[i] = d-I::A[i];
        }
        else if (I::T[i]==3){
            I::B[i] = d-I::A[i];
        }

        if (I::T[i]>=2){
            X.push_back(I::A[i]);
            Y.push_back(I::B[i]);
        }

    }

    compress(X); compress(Y);
    for (int i=1;i<=(int)I::X.size()-1;i++){
        I::X[i] = getidx(X, I::X[i]);
        I::Y[i] = getidx(Y, I::Y[i]);
    }

    for (int i=1;i<=q;i++){
        if (I::T[i]>=2){
            I::A[i] = getidx(X, I::A[i]);
            I::B[i] = getidx(Y, I::B[i]);
        }
    }
    ///

    /*for (int i=1;i<=n;i++){
        treex.update(1, 1, n, i, i, I::X[i]);
        treey.update(1, 1, n, i, i, I::Y[i]);
    }*/

    sort(tmp.begin(), tmp.end());
    for (int i=0;i<n;i++){
        tmp[i].x = getidx(X, tmp[i].x);
        tmp[i].y = getidx(Y, tmp[i].y);

        treex.update(1, 1, n, i+1, i+1, tmp[i].x);
        treey.update(1, 1, n, i+1, i+1, tmp[i].y);
        pos[tmp[i].i] = i+1;

        //printf(" init %d -> %d %d\n", i+1, X[tmp[i].x], Y[tmp[i].y]);
    }
}

int main(){
    input();

    int cnt = I::X.size();
    for (int i=1;i<=q;i++){
        int t = I::T[i], u = I::A[i], v = I::B[i];
        if (t==1){
            printf("%d %d\n", X[treex.query(1, 1, n, pos[u])], Y[treey.query(1, 1, n, pos[u])]);
            continue;
        }
        else if (t==4){
            treex.update(1, 1, n, pos[cnt], pos[cnt], u, 1);
            //printf("         %d(%d) -> %d\n", cnt, pos[cnt], X[treex.query(1, 1, n, pos[cnt])]);
            ++cnt;
            continue;
        }

        int l = 1;
        int r = treey.left_bound(1, 1, n, v)-1;
        if (r==-2) r = n;

        treex.update(1, 1, n, l, r, u);

        //printf("l = %d, r = %d\n", l, r);
        /*if (l>r) continue;

        if (t==2){
            treex.update(1, 1, n, l, r, u);
        }
        if (t==3){
            treey.update(1, 1, n, l, r, v);
        }*/
    }
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2771 ms 72860 KB Output is correct
2 Correct 2616 ms 75220 KB Output is correct
3 Correct 2512 ms 75312 KB Output is correct
4 Correct 2274 ms 74796 KB Output is correct
5 Correct 2295 ms 75132 KB Output is correct
6 Correct 2615 ms 75132 KB Output is correct
7 Correct 2641 ms 75132 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2202 ms 63084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 2202 ms 63084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -