oj.uz

Submission #1046863

# Submission time Handle Problem Language Result Execution time Memory
1046863 2024-08-07T05:15:33 Z 변재우(#11026) Sweeping (JOI20_sweeping) C++17
11 / 100
 1800 ms 74152 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=M+1; cin>>l;
            for(int s=1, e=M; 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, M, N-l);
        }
        else {
            int l, p=0; cin>>l;
            for(int s=1, e=M; 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 Incorrect 7 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 64080 KB Output is correct
2 Correct 1472 ms 73940 KB Output is correct
3 Correct 1203 ms 72876 KB Output is correct
4 Correct 1230 ms 73800 KB Output is correct
5 Correct 1346 ms 73732 KB Output is correct
6 Correct 1428 ms 73812 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 64080 KB Output is correct
2 Correct 1472 ms 73940 KB Output is correct
3 Correct 1203 ms 72876 KB Output is correct
4 Correct 1230 ms 73800 KB Output is correct
5 Correct 1346 ms 73732 KB Output is correct
6 Correct 1428 ms 73812 KB Output is correct
7 Incorrect 1225 ms 74152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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