oj.uz

Submission #1047006

# Submission time Handle Problem Language Result Execution time Memory
1047006 2024-08-07T07:34:16 Z 정희우(#11025) Sweeping (JOI20_sweeping) C++17
0 / 100
 2957 ms 721664 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_Q=1000010;

struct Obj
{
    int x,d,i;
    bool operator < (const Obj &o) const
    {
        if(x!=o.x)return x<o.x;
        return d<o.d;
    }
};

struct Segtree
{
    
    struct Seg
    {
        int xi,yi;
        Seg()
        {
            xi=yi=MAX_Q;
        }
        void upd(int d,int i)
        {
            if(d==0)
                xi=min(xi,i);
            else
                yi=min(yi,i);
        }
    };
    int sz;
    vector<Obj> obj;
    vector<Seg> seg;
    void init_seg(int i,int s,int e)
    {
        if(s+1==e)
        {
            seg[i].upd(obj[s].d,obj[s].i);
            return;
        }
        init_seg(i<<1,s,(s+e)>>1);
        init_seg(i<<1|1,(s+e)>>1,e);
        seg[i].xi=min(seg[i<<1].xi,seg[i<<1|1].xi);
        seg[i].yi=min(seg[i<<1].yi,seg[i<<1|1].yi);
    }
    int findyi(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return MAX_Q;
        if(l<=s && e<=r)return seg[i].yi;
        return min(findyi(i<<1,s,(s+e)>>1,l,r),findyi(i<<1|1,(s+e)>>1,e,l,r));
    }
    int findxi(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return MAX_Q;
        if(l<=s && e<=r)return seg[i].xi;
        return min(findxi(i<<1,s,(s+e)>>1,l,r),findxi(i<<1|1,(s+e)>>1,e,l,r));
    }
    int findx(int i,int s,int e,int l,int r,int j)
    {
        if(s>=r || e<=l || seg[i].xi>=j)return -1;
        if(s+1==e)return s;
        int j2=min(j,findyi(i<<1,s,(s+e)>>1,l,r));
        int v=findx(i<<1|1,(s+e)>>1,e,l,r,j2);
        if(v!=-1)return v;
        return findx(i<<1,s,(s+e)>>1,l,r,j);
    }
    int findy(int i,int s,int e,int l,int r,int j)
    {
        if(s>=r || e<=l || seg[i].yi>=j)return -1;
        if(s+1==e)return s;
        int j2=min(j,findxi(i<<1|1,(s+e)>>1,e,l,r));
        int v=findx(i<<1,s,(s+e)>>1,l,r,j2);
        if(v!=-1)return v;
        return findx(i<<1|1,(s+e)>>1,e,l,r,j);
    }
    void init_()
    {
        sz=obj.size();
        sort(obj.begin(),obj.end());
        seg.resize(sz<<2);
        init_seg(1,0,sz);
    }
    pii calc(pii p)
    {
        int lx=p.first,rx=p.second;
        int l=lower_bound(obj.begin(),obj.end(),(Obj){lx,0,0})-obj.begin();
        int r=upper_bound(obj.begin(),obj.end(),(Obj){rx,1,0})-obj.begin();
        int fx=findx(1,0,sz,l,r,MAX_Q);
        int fy=findy(1,0,sz,l,r,MAX_Q);
        if(fx!=-1)
            lx=obj[fx].x;
        if(fy!=-1)
            rx=obj[fy].x;
        return {lx,rx};
    }
};

int n,m,q;
vector<pii> pos;
vint pin,pout;
vector<Obj> qry;
vint ask;
Segtree sseg[MAX_Q<<2];

void init_(int i,int s,int e)
{
    if(s+1==e)
    {
        sseg[i].obj.push_back(qry[s]);
        sseg[i].init_();
        return;
    }
    init_(i<<1,s,(s+e)>>1);
    init_(i<<1|1,(s+e)>>1,e);
    for(auto o : sseg[i<<1].obj)
        sseg[i].obj.push_back(o);
    for(auto o : sseg[i<<1|1].obj)
        sseg[i].obj.push_back(o);
    sseg[i].init_();
}

pii calc(int i,int s,int e,int l,int r,pii p)
{
    if(s>=r || e<=l)return p;
    if(l<=s && e<=r)return sseg[i].calc(p);
    return calc(i<<1|1,(s+e)>>1,e,l,r,calc(i<<1,s,(s+e)>>1,l,r,p));
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        pos.push_back({x,n-y});
        pin.push_back(0);
        pout.push_back(0);
    }
    for(int i=0;i<q;i++)
    {
        int t,x,y;
        cin >> t >> x;
        if(t==1)
        {
            ask.push_back(x-1);
            pout[x-1]=qry.size();
        }
        else if(t==2)
            qry.push_back((Obj){n-x,0,(int)qry.size()});
        else if(t==3)
            qry.push_back((Obj){x,1,(int)qry.size()});
        else
        {
            cin >> y;
            pos.push_back({x,n-y});
            pin.push_back(qry.size());
            pout.push_back(0);
        }
    }
    int qn=qry.size();
    init_(1,0,qn);
    for(auto i : ask)
    {
        pii p=pos[i];
        p=calc(1,0,qn,pin[i],pout[i],p);
        cout << p.first << ' ' << n-p.second << '\n';
    }
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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