답안 #260923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260923 2020-08-11T08:05:00 Z 최은수(#5044) 청소 (JOI20_sweeping) C++17
64 / 100
7572 ms 302340 KB
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
pi pos[500010];
int gr[500010];
int xmn[1000010],ymn[1000010];
int gct;
struct cmp1
{
    inline bool operator()(const int&x,const int&y)const
    {
        return pi(pos[x].fi,x)<pi(pos[y].fi,y);
    }
};
struct cmp2
{
    inline bool operator()(const int&x,const int&y)const
    {
        return pi(pos[x].se,x)<pi(pos[y].se,y);
    }
};
set<int,cmp1>stx[1000010];
set<int,cmp2>sty[1000010];
set<pi>st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    st.ep(0,0);
    for(int i=0;i++<m;)
    {
        cin>>pos[i].fi>>pos[i].se;
        stx[0].ep(i);
        sty[0].ep(i);
    }
    for(int i=0;i<q;i++)
    {
        int t,l;
        cin>>t>>l;
        if(t==1)
        {
            cout<<max(pos[l].fi,xmn[gr[l]])<<' '<<max(pos[l].se,ymn[gr[l]])<<'\n';
        }
        else if(t==2)
        {
            int g=(--st.upper_bound(pi(n-l,inf)))->se;
            if(stx[g].empty()||xmn[g]==n-l)
                continue;
            vector<int>nx1,nx2;
            auto it1=sty[g].begin(),it2=sty[g].end();
            int par=0,sml=1;
            while(it1!=it2)
            {
                if(par==0)
                {
                    if(pos[*it1].se>l)
                    {
                        sml=0;
                        break;
                    }
                    nx1.eb(*it1);
                    it1++;
                }
                else
                {
                    it2--;
                    if(pos[*it2].se<=l)
                    {
                        sml=1;
                        break;
                    }
                    nx2.eb(*it2);
                }
                par^=1;
            }
            gct++;
            if(sml==0)
            {
                xmn[gct]=n-l;
                ymn[gct]=ymn[g];
                ymn[g]=l+1;
                st.ep(xmn[gct],gct);
                for(int&t:nx1)
                {
                    gr[t]=gct;
                    stx[gct].ep(t);
                    sty[gct].ep(t);
                    stx[g].erase(t);
                    sty[g].erase(t);
                }
            }
            else
            {
                st.erase(pi(xmn[g],g));
                xmn[gct]=xmn[g];
                ymn[gct]=l+1;
                xmn[g]=n-l;
                st.ep(xmn[gct],gct);
                st.ep(xmn[g],g);
                for(int&t:nx2)
                {
                    gr[t]=gct;
                    stx[gct].ep(t);
                    sty[gct].ep(t);
                    stx[g].erase(t);
                    sty[g].erase(t);
                }
            }
        }
        else if(t==3)
        {
            int g=(--st.upper_bound(pi(l+1,inf)))->se;
            if(stx[g].empty()||xmn[g]==l+1)
                continue;
            vector<int>nx1,nx2;
            auto it1=stx[g].begin(),it2=stx[g].end();
            int par=0,sml=1;
            while(it1!=it2)
            {
                if(par==0)
                {
                    if(pos[*it1].fi>l)
                    {
                        sml=0;
                        break;
                    }
                    nx1.eb(*it1);
                    it1++;
                }
                else
                {
                    it2--;
                    if(pos[*it2].fi<=l)
                    {
                        sml=1;
                        break;
                    }
                    nx2.eb(*it2);
                }
                par^=1;
            }
            gct++;
            if(sml==0)
            {
                st.erase(pi(xmn[g],g));
                xmn[gct]=xmn[g];
                ymn[gct]=n-l;
                xmn[g]=l+1;
                st.ep(xmn[gct],gct);
                st.ep(xmn[g],g);
                for(int&t:nx1)
                {
                    gr[t]=gct;
                    stx[gct].ep(t);
                    sty[gct].ep(t);
                    stx[g].erase(t);
                    sty[g].erase(t);
                }
            }
            else
            {
                xmn[gct]=l+1;
                ymn[gct]=ymn[g];
                ymn[g]=n-l;
                st.ep(xmn[gct],gct);
                for(int&t:nx2)
                {
                    gr[t]=gct;
                    stx[gct].ep(t);
                    sty[gct].ep(t);
                    stx[g].erase(t);
                    sty[g].erase(t);
                }
            }
        }
        else
        {
        }
    }
    cout.flush();
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 4462 ms 302340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2460 ms 165384 KB Output is correct
2 Correct 1790 ms 158928 KB Output is correct
3 Correct 1387 ms 170324 KB Output is correct
4 Correct 1434 ms 182188 KB Output is correct
5 Correct 1883 ms 160324 KB Output is correct
6 Correct 1738 ms 158972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2460 ms 165384 KB Output is correct
2 Correct 1790 ms 158928 KB Output is correct
3 Correct 1387 ms 170324 KB Output is correct
4 Correct 1434 ms 182188 KB Output is correct
5 Correct 1883 ms 160324 KB Output is correct
6 Correct 1738 ms 158972 KB Output is correct
7 Correct 7572 ms 179556 KB Output is correct
8 Correct 7228 ms 179496 KB Output is correct
9 Correct 7034 ms 179552 KB Output is correct
10 Correct 3498 ms 179704 KB Output is correct
11 Correct 3015 ms 182880 KB Output is correct
12 Correct 4730 ms 159512 KB Output is correct
13 Correct 4778 ms 161252 KB Output is correct
14 Correct 223 ms 97144 KB Output is correct
15 Correct 2125 ms 160232 KB Output is correct
16 Correct 7445 ms 179936 KB Output is correct
17 Correct 6733 ms 179088 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -