Submission #258878

#	Time	Username	Problem	Language	Result	Execution time	Memory
258878		Kastanda	Sweeping (JOI20_sweeping)	C++11	0 / 100	3192 ms	148176 KiB

sweeping

// M
#include<bits/stdc++.h>
using namespace std;
mt19937 Rnd(time(0));
struct Node
{
        int a[2] = {0, 0}, lz[2] = {0, 0}, id = -1, p = 0;
        Node * l = NULL, * r = NULL;
};
inline bool Less(int * a, int x, int w)
{
        if (w == -1)
                return a[0] < x;
        if (w == -2)
                return a[1] > x;
        return (a[0] < x || (a[0] == x && a[1] > w));
}
inline void Upd(Node * T, int * val)
{
        if (T)
                for (int w = 0; w < 2; w ++)
                        T->a[w] = max(T->a[w], val[w]), T->lz[w] = max(T->lz[w], val[w]);
}
inline void Shift(Node * T)
{
        if (!T)
                return ;
        Upd(T->l, T->lz);
        Upd(T->r, T->lz);
        T->lz[0] = T->lz[1] = 0;
}
void Split(Node * T, Node * &L, Node * &R, int x, int w)
{
        if (!T)
                return void(L = R = NULL);
        Shift(T);
        if (Less(T->a, x, w))
                Split(T->r, T->r, R, x, w), L = T;
        else
                Split(T->l, L, T->l, x, w), R = T;
}
void Merge(Node * &T, Node * L, Node * R)
{
        Shift(L); Shift(R);
        if (!L) T = R;
        else if (!R) T = L;
        else if (L->p > R->p) Merge(L->r, L->r, R), T = L;
        else Merge(R->l, L, R->l), T = R;
}

const int N = 1500006, MXN = 3e6 + 109;
int n, m, q, tscnt, A[N], B[N], TP[N], L[N], nL[N], ST[N], rev[N];
int Last[MXN], MN[MXN * 2];
int Sub2 = 1, Sub4 = 0;
vector < int > U, V[(int)(1e6 + 100)];
pair < int , int > Res[N];
inline int GetMin(int l, int r)
{
        int rt = q + 1;
        l += MXN; r += MXN;
        for (; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1) rt = min(rt, MN[l ++]);
                if (r & 1) rt = min(rt, MN[-- r]);
        }
        return rt;
}
inline void Add(Node * &T, int mxy, int mxx, int * a)
{
        if (!T)
                return ;
        Node * X = NULL, * Y = NULL, * Z = NULL;
        Split(T, X, Y, mxy, -2);
        Split(Y, Y, Z, mxx + 1, -1);
        Upd(Y, a);
        Merge(T, X, Y);
        Merge(T, T, Z);
        return ;
}
inline void Insert(Node * &T, int a, int b, int id)
{
        Node * X = NULL, * Y = NULL, * Z = new Node;
        Split(T, X, Y, a, b);

        Z->a[0] = a;
        Z->a[1] = b;
        Z->lz[0] = Z->lz[1] = 0;
        Z->p = Rnd();
        Z->id = id;

        Merge(T, X, Z);
        Merge(T, T, Y);
        return ;
}
void DFS(Node * T)
{
        if (!T)
                return ;
        DFS(T->l);
        rev[T->id] = ++ tscnt;
        DFS(T->r);
}
pair < int , int > Query(Node * T, int id)
{
        assert(T);
        if (T->id == id)
                return make_pair(T->a[0], T->a[1]);
        if (T->id < id)
                return Query(T->r, id);
        return Query(T->l, id);
}
int main()
{
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= m; i ++)
                scanf("%d%d", &A[i], &B[i]),
                U.push_back(A[i]),
                U.push_back(B[i]);
        int tsm = m;
        for (int i = 1; i <= q; i ++)
        {
                scanf("%d", &TP[i]);
                if (TP[i] == 1) scanf("%d", &L[i]);
                if (TP[i] == 2) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]);
                if (TP[i] == 3) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]), Sub2 = 0;
                if (TP[i] == 4) tsm ++, scanf("%d%d", &A[tsm], &B[tsm]), U.push_back(A[tsm]), U.push_back(B[tsm]), Sub4 = 1;
        }
        assert(Sub4 == 0);

        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        for (int i = 1; i <= tsm; i ++)
        {
                A[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
                B[i] = lower_bound(U.begin(), U.end(), B[i]) - U.begin();
        }
        for (int i = 1; i <= q; i ++)
                if (TP[i] == 2 || TP[i] == 3)
                        nL[i] = lower_bound(U.begin(), U.end(), n - L[i]) - U.begin(),
                        L[i] = lower_bound(U.begin(), U.end(), L[i]) - U.begin();


        fill(Last, Last + MXN, q + 1);
        for (int i = q; i; i --)
        {
                if (TP[i] != 2 && TP[i] != 3)
                        continue;
                if (TP[i] == 2)
                        Last[L[i]] = i;
                if (TP[i] == 3)
                        Last[nL[i]] = i;
        }
        for (int i = 0; i < (int)U.size(); i ++)
                MN[i + MXN] = Last[i];
        for (int i = MXN - 1; i; i --)
                MN[i] = min(MN[i << 1], MN[i << 1 ^ 1]);
        for (int i = 1; i <= m; i ++)
        {
                int l = B[i];
                int r = upper_bound(U.begin(), U.end(), n - A[i]) - U.begin();
                ST[i] = GetMin(l, r);
                V[ST[i]].push_back(i);
        }

        Node * T = NULL;
        for (int i = 1; i <= q; i ++)
        {
                if (TP[i] == 1)
                {
                        if (ST[L[i]] > i)
                                Res[i] = {A[L[i]], B[L[i]]};
                        continue;
                }
                if (TP[i] == 2)
                {
                        int a[2] = {nL[i], 0};
                        Add(T, L[i], nL[i], a);// [y, x]
                }
                if (TP[i] == 3)
                {
                        int a[2] = {0, nL[i]};
                        Add(T, nL[i], L[i], a);// [y, x]
                }
                for (int j : V[i])
                {
                        int a = A[j], b = B[j];
                        if (TP[i] == 2)
                                a = max(a, nL[i]);
                        if (TP[i] == 3)
                                b = max(b, nL[i]);
                        Insert(T, a, b, j);
                }
        }
        DFS(T);

        T = NULL;
        for (int i = 1; i <= q; i ++)
        {
                if (TP[i] == 1)
                {
                        if (ST[L[i]] > i)
                                Res[i] = {A[L[i]], B[L[i]]};
                        else
                                Res[i] = Query(T, rev[L[i]]);
                        continue;
                }
                if (TP[i] == 2)
                {
                        int a[2] = {nL[i], 0};
                        Add(T, L[i], nL[i], a);// [y, x]
                }
                if (TP[i] == 3)
                {
                        int a[2] = {0, nL[i]};
                        Add(T, nL[i], L[i], a);// [y, x]
                }
                for (int j : V[i])
                {
                        int a = A[j], b = B[j];
                        if (TP[i] == 2)
                                a = max(a, nL[i]);
                        if (TP[i] == 3)
                                b = max(b, nL[i]);
                        Insert(T, a, b, rev[j]);
                }
        }
        for (int i = 1; i <= q; i ++)
                if (TP[i] == 1)
                {
                        printf("%d %d\n", U[Res[i].first], U[Res[i].second]);
                }
        return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &n, &m, &q);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:117:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &A[i], &B[i]),
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 U.push_back(A[i]),
                 ~~~~~~~~~~~~~~~~~^~
                 U.push_back(B[i]);
                 ~~~~~~~~~~~~~~~~~ 
sweeping.cpp:122:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &TP[i]);
                 ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:123:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 if (TP[i] == 1) scanf("%d", &L[i]);
                                 ~~~~~^~~~~~~~~~~~~
sweeping.cpp:124:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 if (TP[i] == 2) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]);
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:125:93: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 if (TP[i] == 3) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]), Sub2 = 0;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
sweeping.cpp:126:114: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 if (TP[i] == 4) tsm ++, scanf("%d%d", &A[tsm], &B[tsm]), U.push_back(A[tsm]), U.push_back(B[tsm]), Sub4 = 1;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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