oj.uz

Submission #1047218

# Submission time Handle Problem Language Result Execution time Memory
1047218 2024-08-07T10:52:51 Z heeew Sweeping (JOI20_sweeping) C++14
100 / 100
 3643 ms 1216388 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==e)return;
    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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 220496 KB Output is correct
2 Correct 35 ms 220752 KB Output is correct
3 Correct 29 ms 219736 KB Output is correct
4 Correct 34 ms 220508 KB Output is correct
5 Correct 32 ms 221524 KB Output is correct
6 Correct 32 ms 220764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3280 ms 640436 KB Output is correct
2 Correct 3309 ms 640376 KB Output is correct
3 Correct 3172 ms 638928 KB Output is correct
4 Correct 1159 ms 639036 KB Output is correct
5 Correct 1363 ms 639280 KB Output is correct
6 Correct 1870 ms 638416 KB Output is correct
7 Correct 3359 ms 639888 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3592 ms 720044 KB Output is correct
2 Correct 3643 ms 719580 KB Output is correct
3 Correct 1870 ms 719316 KB Output is correct
4 Correct 2429 ms 719832 KB Output is correct
5 Correct 3466 ms 719892 KB Output is correct
6 Correct 3632 ms 719792 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3592 ms 720044 KB Output is correct
2 Correct 3643 ms 719580 KB Output is correct
3 Correct 1870 ms 719316 KB Output is correct
4 Correct 2429 ms 719832 KB Output is correct
5 Correct 3466 ms 719892 KB Output is correct
6 Correct 3632 ms 719792 KB Output is correct
7 Correct 3440 ms 719736 KB Output is correct
8 Correct 3450 ms 719776 KB Output is correct
9 Correct 3409 ms 719920 KB Output is correct
10 Correct 2016 ms 719216 KB Output is correct
11 Correct 2434 ms 719792 KB Output is correct
12 Correct 3434 ms 719748 KB Output is correct
13 Correct 3571 ms 719852 KB Output is correct
14 Correct 1273 ms 1216388 KB Output is correct
15 Correct 280 ms 256716 KB Output is correct
16 Correct 3465 ms 739796 KB Output is correct
17 Correct 2016 ms 739416 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 220496 KB Output is correct
2 Correct 35 ms 220752 KB Output is correct
3 Correct 29 ms 219736 KB Output is correct
4 Correct 34 ms 220508 KB Output is correct
5 Correct 32 ms 221524 KB Output is correct
6 Correct 32 ms 220764 KB Output is correct
7 Correct 3280 ms 640436 KB Output is correct
8 Correct 3309 ms 640376 KB Output is correct
9 Correct 3172 ms 638928 KB Output is correct
10 Correct 1159 ms 639036 KB Output is correct
11 Correct 1363 ms 639280 KB Output is correct
12 Correct 1870 ms 638416 KB Output is correct
13 Correct 3359 ms 639888 KB Output is correct
14 Correct 3592 ms 720044 KB Output is correct
15 Correct 3643 ms 719580 KB Output is correct
16 Correct 1870 ms 719316 KB Output is correct
17 Correct 2429 ms 719832 KB Output is correct
18 Correct 3466 ms 719892 KB Output is correct
19 Correct 3632 ms 719792 KB Output is correct
20 Correct 3440 ms 719736 KB Output is correct
21 Correct 3450 ms 719776 KB Output is correct
22 Correct 3409 ms 719920 KB Output is correct
23 Correct 2016 ms 719216 KB Output is correct
24 Correct 2434 ms 719792 KB Output is correct
25 Correct 3434 ms 719748 KB Output is correct
26 Correct 3571 ms 719852 KB Output is correct
27 Correct 1273 ms 1216388 KB Output is correct
28 Correct 280 ms 256716 KB Output is correct
29 Correct 3465 ms 739796 KB Output is correct
30 Correct 2016 ms 739416 KB Output is correct
31 Correct 2424 ms 660436 KB Output is correct
32 Correct 3358 ms 660792 KB Output is correct
33 Correct 3018 ms 660772 KB Output is correct
34 Correct 2579 ms 656712 KB Output is correct
35 Correct 2684 ms 657416 KB Output is correct
36 Correct 1901 ms 660112 KB Output is correct
37 Correct 2246 ms 660020 KB Output is correct
38 Correct 3474 ms 658336 KB Output is correct
39 Correct 3617 ms 659668 KB Output is correct
40 Correct 3523 ms 659804 KB Output is correct