oj.uz

답안 #1047113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047113 2024-08-07T09:02:29 Z 정희우(#11025) 청소 (JOI20_sweeping) C++17
21 / 100
 3571 ms 902064 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;
    }
};

int max_i(int i,int s,int e)
{
    if(s+1==e)
        return i;
    return max_i(i<<1|1,(s+e)>>1,e);
}

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(max_i(1,0,sz)+1);
        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 37 ms 220240 KB Output is correct
2 Correct 34 ms 220492 KB Output is correct
3 Runtime error 152 ms 445268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3205 ms 551632 KB Output is correct
2 Correct 3271 ms 571364 KB Output is correct
3 Correct 3197 ms 571444 KB Output is correct
4 Correct 1142 ms 571192 KB Output is correct
5 Correct 1295 ms 570928 KB Output is correct
6 Correct 1982 ms 570436 KB Output is correct
7 Correct 3354 ms 571144 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3493 ms 570512 KB Output is correct
2 Correct 3571 ms 590216 KB Output is correct
3 Correct 1864 ms 589124 KB Output is correct
4 Correct 2374 ms 589968 KB Output is correct
5 Correct 3498 ms 590128 KB Output is correct
6 Correct 3567 ms 590000 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3493 ms 570512 KB Output is correct
2 Correct 3571 ms 590216 KB Output is correct
3 Correct 1864 ms 589124 KB Output is correct
4 Correct 2374 ms 589968 KB Output is correct
5 Correct 3498 ms 590128 KB Output is correct
6 Correct 3567 ms 590000 KB Output is correct
7 Correct 3350 ms 590188 KB Output is correct
8 Correct 3392 ms 590340 KB Output is correct
9 Correct 3460 ms 590204 KB Output is correct
10 Correct 1868 ms 589060 KB Output is correct
11 Correct 2398 ms 588008 KB Output is correct
12 Correct 3426 ms 588144 KB Output is correct
13 Correct 3361 ms 571232 KB Output is correct
14 Correct 1004 ms 902064 KB Output is correct
15 Runtime error 289 ms 496944 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 220240 KB Output is correct
2 Correct 34 ms 220492 KB Output is correct
3 Runtime error 152 ms 445268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -