oj.uz

답안 #1047128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047128 2024-08-07T09:10:11 Z heeew 청소 (JOI20_sweeping) C++14
21 / 100
 3676 ms 1216260 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 33 ms 220504 KB Output is correct
2 Correct 33 ms 220752 KB Output is correct
3 Runtime error 147 ms 445148 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3320 ms 638668 KB Output is correct
2 Correct 3304 ms 638688 KB Output is correct
3 Correct 3233 ms 637756 KB Output is correct
4 Correct 1211 ms 638024 KB Output is correct
5 Correct 1346 ms 638768 KB Output is correct
6 Correct 1831 ms 637980 KB Output is correct
7 Correct 3421 ms 640172 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3645 ms 719768 KB Output is correct
2 Correct 3664 ms 720216 KB Output is correct
3 Correct 1818 ms 719384 KB Output is correct
4 Correct 2428 ms 719728 KB Output is correct
5 Correct 3590 ms 719760 KB Output is correct
6 Correct 3596 ms 719792 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3645 ms 719768 KB Output is correct
2 Correct 3664 ms 720216 KB Output is correct
3 Correct 1818 ms 719384 KB Output is correct
4 Correct 2428 ms 719728 KB Output is correct
5 Correct 3590 ms 719760 KB Output is correct
6 Correct 3596 ms 719792 KB Output is correct
7 Correct 3409 ms 719912 KB Output is correct
8 Correct 3498 ms 719896 KB Output is correct
9 Correct 3511 ms 719816 KB Output is correct
10 Correct 1944 ms 719520 KB Output is correct
11 Correct 2576 ms 719700 KB Output is correct
12 Correct 3486 ms 719664 KB Output is correct
13 Correct 3676 ms 719924 KB Output is correct
14 Correct 1201 ms 1216260 KB Output is correct
15 Runtime error 301 ms 496884 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 220504 KB Output is correct
2 Correct 33 ms 220752 KB Output is correct
3 Runtime error 147 ms 445148 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -