oj.uz

답안 #1047064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047064 2024-08-07T08:25:51 Z 정희우(#11025) 청소 (JOI20_sweeping) C++17
21 / 100
 3753 ms 2097152 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 merge_(Seg &p,const Seg &l,const Seg &r)
    {
        p.xi=l.xi;
        if(l.yi>r.xi)p.xi=min(p.xi,r.xi);
        p.yi=r.yi;
        if(r.xi>l.yi)p.yi=min(p.yi,l.yi);
    }
    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);
        merge_(seg[i],seg[i<<1],seg[i<<1|1]);
    }
    Seg find_(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return {};
        if(l<=s && e<=r)return seg[i];
        Seg v;
        merge_(v,find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
        return v;
    }
    int findx(int i,int s,int e,int l,int r,Seg j)
    {
        if(s>=r || e<=l)return -1;
        if(l<=s && e<=r && seg[i].xi>=j.yi)return -1;
        if(s+1==e)return s;
        Seg j2;
        merge_(j2,j,find_(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,Seg j)
    {
        if(s>=r || e<=l)return -1;
        if(l<=s && e<=r && seg[i].yi>=j.xi)return -1;
        if(s+1==e)return s;
        Seg j2;
        merge_(j2,find_(i<<1|1,(s+e)>>1,e,l,r),j);
        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);
        Seg v;
    }
    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,(Seg){});
        int fy=findy(1,0,sz,l,r,(Seg){});
        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 34 ms 220504 KB Output is correct
2 Correct 34 ms 220760 KB Output is correct
3 Runtime error 1046 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3502 ms 642528 KB Output is correct
2 Correct 3608 ms 649948 KB Output is correct
3 Correct 3378 ms 660728 KB Output is correct
4 Correct 1304 ms 658196 KB Output is correct
5 Correct 1382 ms 660500 KB Output is correct
6 Correct 1959 ms 660768 KB Output is correct
7 Correct 3403 ms 659652 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3673 ms 733876 KB Output is correct
2 Correct 3675 ms 739392 KB Output is correct
3 Correct 1902 ms 738428 KB Output is correct
4 Correct 2500 ms 739168 KB Output is correct
5 Correct 3623 ms 739248 KB Output is correct
6 Correct 3753 ms 739640 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3673 ms 733876 KB Output is correct
2 Correct 3675 ms 739392 KB Output is correct
3 Correct 1902 ms 738428 KB Output is correct
4 Correct 2500 ms 739168 KB Output is correct
5 Correct 3623 ms 739248 KB Output is correct
6 Correct 3753 ms 739640 KB Output is correct
7 Correct 3521 ms 739508 KB Output is correct
8 Correct 3520 ms 720036 KB Output is correct
9 Correct 3514 ms 719768 KB Output is correct
10 Correct 2017 ms 719316 KB Output is correct
11 Correct 2511 ms 719960 KB Output is correct
12 Correct 3490 ms 719660 KB Output is correct
13 Correct 3606 ms 719752 KB Output is correct
14 Correct 1183 ms 1215828 KB Output is correct
15 Runtime error 924 ms 2097152 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 220504 KB Output is correct
2 Correct 34 ms 220760 KB Output is correct
3 Runtime error 1046 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -