oj.uz

Submission #1047089

# Submission time Handle Problem Language Result Execution time Memory
1047089 2024-08-07T08:51:01 Z 변재우(#11026) Sweeping (JOI20_sweeping) C++17
10 / 100
 701 ms 110920 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=1000010, S=(1<<22);
int N, M, M0, Q, I[Nmax], II[Nmax];
pair<int, int> A[Nmax];
pair<int, pair<int, int>> X[Nmax];
vector<pair<int, int>> V;

class Lazy {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    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) {
        if(s==e) {
            if(Tree[node]>=0) Tree[node]=max(Tree[node], Lazy[node]);
        }
        else Lazy[node<<1]=max(Lazy[node<<1], Lazy[node]), Lazy[node<<1|1]=max(Lazy[node<<1|1], Lazy[node]);
        Lazy[node]=0;
        return;
    }
    void Update(int node, int s, int e, int k, int v) {
        Propagate(node, s, e);
        if(s==e) {
            Tree[node]=v; return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
    }
    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);
    }
    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);
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>Q;
    for(int i=1; i<=M; i++) cin>>A[i].first>>A[i].second, V.push_back({A[i].second, i});
    M0=M;
    for(int i=1; i<=Q; i++) {
        cin>>X[i].first>>X[i].second.first;
        if(X[i].first==4) {
            cin>>X[i].second.second, V.push_back({X[i].second.second, ++M});
            A[M]={X[i].second.first, X[i].second.second};
        }
    }
    sort(V.begin(), V.end());
    for(int i=0; i<M; i++) I[V[i].second]=i+1, II[i+1]=V[i].second;
    for(int i=M0+1; i<=M; i++) T.Update(I[i], -1);
    for(int i=1; i<=Q; i++) {
        if(X[i].first==1) {
            int k=X[i].second.first;
            cout<<max(A[k].first, T.Query(I[k]))<<" "<<A[k].second<<"\n";
        }
        else if(X[i].first==2) {
            int l=X[i].second.first, p=0;
            for(int s=1, e=M; s<=e; ) {
                int m=(s+e)/2;
                if(A[II[m]].second<=l) p=m, s=m+1;
                else e=m-1;
            }
            T.Update(1, p, N-l);
        }
        else if(X[i].first==4) {
            ++M0;
            T.Update(I[M0], A[M0].first);
        }
    }
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 11104 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 701 ms 110920 KB Output is correct
2 Correct 671 ms 101152 KB Output is correct
3 Correct 599 ms 90796 KB Output is correct
4 Correct 450 ms 90068 KB Output is correct
5 Correct 448 ms 89260 KB Output is correct
6 Correct 548 ms 89264 KB Output is correct
7 Correct 611 ms 89096 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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