oj.uz

Submission #1046862

# Submission time Handle Problem Language Result Execution time Memory
1046862 2024-08-07T05:14:26 Z 변재우(#11026) Sweeping (JOI20_sweeping) C++17
0 / 100
 71 ms 35300 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=1500010, S=(1<<21);
int N, M, Q, X[Nmax], Y[Nmax];
class Seg {
public:
    void Update(int l, int r, int v) {Update(1, 1, S, l, r, v);}
    int Query(int k) {return Query(1, 1, S, k);}
private:
    int Tree[2*S], Lazy[2*S];
    void Propagate(int node, int s, int e) {
        Tree[node]=max(Tree[node], Lazy[node]);
        if(s!=e) Lazy[node<<1]=max(Lazy[node<<1], Lazy[node]), Lazy[node<<1|1]=max(Lazy[node<<1|1], Lazy[node]);
        return;
    }
    void Update(int node, int s, int e, int l, int r, int v) {
        Propagate(node, s, e);
        if(s>r || l>e) return;
        if(l<=s && e<=r) {
            Lazy[node]=v;
            Propagate(node, s, e);
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        Update(lch, s, m, l, r, v), Update(rch, m+1, e, l, r, v);
        Tree[node]=max(Tree[lch], Tree[rch]);
    }
    int Query(int node, int s, int e, int k) {
        Propagate(node, s, e);
        if(s==e) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) return Query(lch, s, m, k);
        else return Query(rch, m+1, e, k);
    }
}Tx, Ty;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>Q;
    for(int i=1; i<=M; i++) cin>>X[i]>>Y[i];
    for(int i=1; i<=Q; i++) {
        int op; cin>>op;
        if(op==1)  {
            int k; cin>>k;
            cout<<max(X[k], Tx.Query(k))<<" "<<max(Y[k], Ty.Query(k))<<"\n";
        }
        else if(op==2) {
            int l, p=N+1; cin>>l;
            for(int s=1, e=N; s<=e; ) {
                int m=(s+e)/2;
                if(max(Y[m], Ty.Query(m))<=l) p=m, e=m-1;
                else s=m+1;
            }
            Tx.Update(p, N, N-l);
        }
        else {
            int l, p=0; cin>>l;
            for(int s=1, e=N; s<=e; ) {
                int m=(s+e)/2;
                if(max(X[m], Tx.Query(m))<=l) p=m, s=m+1;
                else e=m-1;
            }
            Ty.Update(1, p, N-l);
        }
    }
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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