oj.uz

답안 #1047036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047036 2024-08-07T07:57:04 Z 정희우(#11025) 청소 (JOI20_sweeping) C++17
10 / 100
 3510 ms 719704 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=i;
            else 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=findy(i<<1,s,(s+e)>>1,l,r,j2);
        if(v!=-1)return v;
        return findy(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};
    }
};

struct Ask
{
    pii p;
    int l,r;
};


int n,m,q;
vector<pii> pos;
vint pin;
vector<Obj> qry;
vector<Ask> 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);
    }
    for(int i=0;i<q;i++)
    {
        int t,x,y;
        cin >> t >> x;
        if(t==1)
            ask.push_back({pos[x-1],pin[x-1],(int)qry.size()});
        else if(t==2)
            qry.push_back({n-x,0,(int)qry.size()});
        else if(t==3)
            qry.push_back({x,1,(int)qry.size()});
        else
        {
            cin >> y;
            pos.push_back({x,n-y});
            pin.push_back(qry.size());
        }
    }
    int qn=qry.size();
    init_(1,0,qn);
    for(auto a : ask)
    {
        pii p=calc(1,0,qn,a.l,a.r,a.p);
        cout << p.first << ' ' << n-p.second << '\n';
    }
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 220504 KB Output is correct
2 Incorrect 33 ms 220768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2407 ms 639144 KB Output is correct
2 Correct 2304 ms 641648 KB Output is correct
3 Correct 2315 ms 639028 KB Output is correct
4 Correct 1092 ms 638396 KB Output is correct
5 Correct 1121 ms 639656 KB Output is correct
6 Correct 1255 ms 636948 KB Output is correct
7 Correct 2390 ms 640408 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3510 ms 719704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3510 ms 719704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 220504 KB Output is correct
2 Incorrect 33 ms 220768 KB Output isn't correct
3 Halted 0 ms 0 KB -