oj.uz

Submission #616904

# Submission time Handle Problem Language Result Execution time Memory
616904 2022-08-01T07:36:43 Z 박상훈(#8502) Sweeping (JOI20_sweeping) C++17
11 / 100
 2411 ms 70148 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){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] = x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        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;

int n, q;

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);

    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]);
    }

    for (int i=1;i<=q;i++){
        cin >> I::T[i] >> I::A[i];
        if (I::T[i]==4){
            cin >> 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<=n;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]);
    }
}

int main(){
    input();

    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, u)], Y[treey.query(1, 1, n, u)]);
            continue;
        }

        int l = treey.right_bound(1, 1, n, v)+1;
        int r = treex.left_bound(1, 1, n, u)-1;
        if (l==0) l = 1;
        if (r==-2) r = n;
        //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 Runtime error 8 ms 1024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 818 ms 48440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2031 ms 50384 KB Output is correct
2 Correct 2411 ms 70148 KB Output is correct
3 Correct 1977 ms 68996 KB Output is correct
4 Correct 2231 ms 69964 KB Output is correct
5 Correct 2027 ms 69904 KB Output is correct
6 Correct 2339 ms 70104 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2031 ms 50384 KB Output is correct
2 Correct 2411 ms 70148 KB Output is correct
3 Correct 1977 ms 68996 KB Output is correct
4 Correct 2231 ms 69964 KB Output is correct
5 Correct 2027 ms 69904 KB Output is correct
6 Correct 2339 ms 70104 KB Output is correct
7 Incorrect 2182 ms 70068 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -