Submission #217037

#	Time	Username	Problem	Language	Result	Execution time	Memory
217037		combi1k1	Sweeping (JOI20_sweeping)	C++14	0 / 100	4118 ms	145092 KiB

sweeping

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 1500005;

typedef pair<int,int>   ii;
typedef vector<int>     vi;

struct DSU  {
    vector<int> val;
    vector<vi>  vec;

    int par[N];

    void init() {
        val.clear();
        vec.clear();
    }
    int add(int x,int v)    {
        int idx = sz(val);

        val.push_back(x);
        vec.push_back({});

        if (v >= 0) {
            par[v] = idx;
            vec.back().pb(v);
        }
        return  idx;
    }
    int join(int x,int y)   {
        if (sz(vec[x]) < sz(vec[y]))
            swap(x,y);

        val[x] = max(val[x],val[y]);

        for(int u : vec[y])
            par[u] = x,
            vec[x].pb(u);

        return  x;
    }
}   fX, fY;

typedef array<int,3>    ar;

ii  ans[N];
ii  pos[N];
int n, m, q;

bool done[N];

void getReal(int i) {
    pos[i].X = fX.val[fX.par[i]];
    pos[i].Y = fY.val[fY.par[i]];
}

void calc(int x,int y,vector<ar> vec)   {
    if (vec.empty())
        return;

    int dif = n - x - y;

    if (dif == 0)   {
        for(ar  a : vec)
            if (a[0] == 1)
                ans[a[2]].X = x,
                ans[a[2]].Y = y;

        return;
    }
    fX.init();
    fY.init();

    int X = x + (dif + 1) / 2;
    int Y = y + (dif + 2) / 2;

    vector<ar>  vecU;
    vector<ar>  vecR;

    multiset<ii>    Sx;
    multiset<ii>    Sy;

    for(ar  a : vec)    {
        if (a[0] == 1)  {
            int i = a[1];
            if (pos[i].Y >= Y)  {   vecU.pb(a); continue;   }
            if (pos[i].X >= X)  {   vecR.pb(a); continue;   }

            ans[i].X = fX.val[fX.par[i]];
            ans[i].Y = fY.val[fY.par[i]];
        }
        if (a[0] == 2)  {
            if (a[1] >= Y)  {
                int nxt = n - a[1];
                int idx = fX.add(nxt,-1);

                while (Sx.size() && (*Sx.begin()).X <= nxt) {
                    int x = (*Sx.begin()).Y;
                    Sx.erase( Sx.begin());

                    idx = fX.join(idx,x);
                }
                Sx.insert(ii(fX.val[idx],idx));
                vecU.pb(a);
            }
            else    {
                while (Sy.size() && (*Sy.begin()).X <= a[1])    {
                    int x = (*Sy.begin()).Y;
                    Sy.erase( Sy.begin());

                    for(int u : fY.vec[x])
                        if(!done[u])    {
                            done[u] = 1;
                            getReal(u);
                            pos[u].X = n - a[1];
                            vecR.push_back({4,u,0});
                        }
                }
                vecR.pb(a);
            }
        }
        if (a[0] == 3)  {
            if (a[1] >= X)  {
                int nxt = n - a[1];
                int idx = fY.add(nxt,-1);

                while (Sy.size() && (*Sy.begin()).X <= nxt) {
                    int x = (*Sy.begin()).Y;
                    Sy.erase( Sy.begin());

                    idx = fY.join(idx,x);
                }
                Sy.insert(ii(fY.val[idx],idx));
                vecR.pb(a);
            }
            else    {
                while (Sx.size() && (*Sx.begin()).X <= a[1])    {
                    int x = (*Sx.begin()).Y;
                    Sx.erase( Sx.begin());

                    for(int u : fX.vec[x])
                        if(!done[u])    {
                            done[u] = 1;
                            getReal(u);
                            pos[u].Y = n - a[1];
                            vecU.push_back({4,u,0});
                        }
                }
                vecU.pb(a);
            }
        }
        if (a[0] == 4)  {
            int i = a[1];
            done[i] = 0;

            if (pos[i].Y >= Y)  {   done[i] = 1; vecU.pb(a); continue;  }
            if (pos[i].X >= X)  {   done[i] = 1; vecR.pb(a); continue;  }

            int xv = fX.add(pos[i].X,i);
            int yv = fY.add(pos[i].Y,i);

            Sx.insert(ii(fX.val[xv],xv));
            Sy.insert(ii(fY.val[yv],yv));
        }
    }
    calc(x,Y,vecU);
    calc(X,y,vecR);
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;

    vector<ar>  Que;

    int tot = 0;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        pos[++tot] = ii(x,y);
        Que.push_back({4,tot,0});
    }
    for(int i = 0 ; i < q ; ++i)    {
        ans[i] = ii(-1,-1);
        int t;  cin >> t;

        if (t < 4)  {
            int x;  cin >> x;
            Que.push_back({t,x,i});
        }
        else    {
            int x;  cin >> x;
            int y;  cin >> y;

            pos[++tot] = ii(x,y);
            Que.push_back({4,tot,i});
        }
    }
    calc(0,0,Que);

    for(int i = 0 ; i < q ; ++i)
        if (ans[i].X >= 0)
            cout << ans[i].X << " ",
            cout << ans[i].Y << "\n";
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25