제출 #231153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231153		duality	청소 (JOI20_sweeping)	C++11	75 / 100	18047 ms	1449336 KiB

sweeping

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const pair<T1,T2> &p) {
    output << "(" << p.first << "," << p.second << ")";
    return output;
}
template<typename T>
ostream& operator<<(ostream& output,const vector<T> &v) {
    unsigned int i;
    bool f = 1;
    for (i = 0; i < v.size(); i++) {
        if (!f) output << " ";
        output << v[i];
        f = 0;
    }

    return output;
}
template<typename T>
ostream& operator<<(ostream& output,const list<T> &l) {
    typename list<T>::const_iterator it;
    bool f = 1;
    for (it = l.begin(); it != l.end(); it++) {
        if (!f) output << " ";
        output << *it;
        f = 0;
    }

    return output;
}
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const map<T1,T2> &m) {
    typename map<T1,T2>::const_iterator it;
    bool f = 1;
    for (it = m.begin(); it != m.end(); it++) {
        if (!f) output << " ";
        output << "(" << it->first << " -> " << it->second << ")";
        f = 0;
    }

    return output;
}
template<typename T>
ostream& operator<<(ostream& output,const set<T> &s) {
    typename set<T>::const_iterator it;
    bool f = 1;
    for (it = s.begin(); it != s.end(); it++) {
        if (!f) output << " ";
        output << *it;
        f = 0;
    }

    return output;
}



int X[1500000],Y[1500000];
map<int,pii> MM;
struct func { int l,r,d,u,x,y; };
vector<func> f;
int insert(map<pii,pii> &M,int l,int r,pii p) {
    //debug "here",l,r,p;
    //debug M;
    auto it = M.upper_bound(mp(l,2e9));
    if (it != M.begin()) {
        it--;
        pair<pii,pii> q = *it;
        if ((q.first.first <= l) && (l <= q.first.second)) {
            M.erase(it);
            if (l-1 >= q.first.first) M[mp(q.first.first,l-1)] = q.second;
            M[mp(l,q.first.second)] = q.second;
        }
    }
    //debug M;
    it = M.upper_bound(mp(r,2e9));
    if (it != M.begin()) {
        it--;
        pair<pii,pii> q = *it;
        if ((q.first.first <= r) && (r <= q.first.second)) {
            M.erase(it);
            if (r+1 <= q.first.second) M[mp(r+1,q.first.second)] = q.second;
            M[mp(q.first.first,r)] = q.second;
        }
    }
    //debug M;
    it = M.lower_bound(mp(l,0));
    while ((it != M.end()) && (it->first.second <= r)) assert(it->first.second >= l),it = M.erase(it);
    M[mp(l,r)] = p;
    //debug M;
    return 0;
}
struct node {
    node *l,*r;
    map<pii,pii> M;
    int update(int s,int e,int as,int ae,int d,int u,pii p) {
        //cout<<as<<","<<ae<<","<<d<<","<<u<<": "<<p.first<<","<<p.second<<endl;
        //cout<<s<<","<<e<<endl;
        if ((s >= as) && (e <= ae)) {
            insert(M,d,u,p);
            return 0;
        }

        int mid = (s+e) / 2;
        if (as <= mid) {
            if (l == NULL) l = new node(),l->l = l->r = NULL;
            l->update(s,mid,as,ae,d,u,p);
        }
        if (ae >= mid+1) {
            if (r == NULL) r = new node(),r->l = r->r = NULL;
            r->update(mid+1,e,as,ae,d,u,p);
        }
        return 0;
    }
    pii query(int s,int e,int q,int qy) {
        int mid = (s+e) / 2;
        pii ans = mp(-1,-1);
        auto it = M.upper_bound(mp(qy,2e9));
        if (it != M.begin()) {
            it--;
            if ((it->first.first <= qy) && (qy <= it->first.second)) ans = it->second;
        }
        if (q <= mid) {
            if (l != NULL) {
                pii ans2 = l->query(s,mid,q,qy);
                if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
            }
        }
        else {
            if (r != NULL) {
                pii ans2 = r->query(mid+1,e,q,qy);
                if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
            }
        }
        return ans;
    }
};
node *root;
int update(int x,int t,int N) {
    auto it = MM.lower_bound(x);
    if (it->first == x) return 0;
    auto it2 = it;
    it2--;
    if (t == 1) {
        f.pb((func){it2->first-it2->second.first,x-1,N-it->first,N-x-1,x,-1});
        f.pb((func){it2->first-it2->second.first,x-1,N-it->first-it->second.second,N-it->first,x,N-it->first});
        MM[x] = mp(it2->second.first+x-it2->first,0);
    }
    else {
        f.pb((func){it2->first,x-1,N-it->first-it->second.second,N-x-1,-1,N-x});
        f.pb((func){it2->first-it2->second.first,it2->first,N-it->first-it->second.second,N-x-1,it2->first,N-x});
        MM[x] = mp(0,it->second.second+it->first-x);
    }
    func a = f[f.size()-2],b = f.back();
    swap(a,b);
    assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
    if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
    swap(a,b);assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
    if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
    return 0;
}
vpii ops;
int t[1000000],p[1000000],l[1000000],a[1000000],b[1000000];
int tree[1 << 22],lazy[1 << 22];
int prop(int s,int e,int i) {
    tree[i] = max(tree[i],lazy[i]);
    if (s != e) {
        lazy[2*i+1] = max(lazy[2*i+1],lazy[i]);
        lazy[2*i+2] = max(lazy[2*i+2],lazy[i]);
    }
    lazy[i] = 0;
    return 0;
}
int update(int s,int e,int as,int ae,int i,int num,int t) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        lazy[i] = num;
        if (t) tree[i] = num;
        prop(s,e,i);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,num,t),update(mid+1,e,as,ae,2*i+2,num,t);
    tree[i] = max(tree[2*i+1],tree[2*i+2]);
    return 0;
}
int query(int s,int e,int qs,int qe,int i) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return 0;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
int main() {
    int i;
    int N,M,Q;
    int T,P,L,A,B,sub2 = 1;
    scanf("%d %d %d",&N,&M,&Q);
    for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
    for (i = 0; i < Q; i++) {
        scanf("%d",&t[i]);
        if (t[i] == 1) scanf("%d",&p[i]);
        else if (t[i] <= 3) scanf("%d",&l[i]);
        else scanf("%d %d",&a[i],&b[i]);
        if (t[i] == 3) sub2 = 0;
    }

    if (sub2) {
        vpii possy;
        int c = M;
        for (i = 0; i < M; i++) possy.pb(mp(Y[i],i));
        for (i = 0; i < Q; i++) {
            if (t[i] == 4) possy.pb(mp(b[i],c++));
        }
        sort(possy.begin(),possy.end());
        for (i = 0; i < M; i++) {
            int x = lower_bound(possy.begin(),possy.end(),mp(Y[i],i))-possy.begin();
            update(0,c-1,x,x,0,X[i],1);
        }
        int c2 = M;
        for (i = 0; i < Q; i++) {
            if (t[i] == 1) {
                int x = lower_bound(possy.begin(),possy.end(),mp(Y[p[i]-1],p[i]-1))-possy.begin();
                printf("%d %d\n",query(0,c-1,x,x,0),Y[p[i]-1]);
            }
            else if (t[i] == 2) {
                int x = upper_bound(possy.begin(),possy.end(),mp(l[i],(int) 2e9))-possy.begin()-1;
                update(0,c-1,0,x,0,N-l[i],0);
            }
            else {
                X[c2] = a[i],Y[c2++] = b[i];
                int x = lower_bound(possy.begin(),possy.end(),mp(Y[c2-1],c2-1))-possy.begin();
                update(0,c-1,x,x,0,X[c2-1],1);
            }
        }
        return 0;
    }

    MM[0] = MM[N+1] = mp(0,0);
    root = new node;
    root->l = root->r = NULL;
    for (i = 0; i < Q; i++) {
        T = t[i];
        if (T == 1) {
            P = p[i],P--;
            pii ans = root->query(0,N+6,X[P],Y[P]);
            int xx = X[P],yy = Y[P];
            if (ans.first != -1) xx = ans.first;
            if (ans.second != -1) yy = ans.second;
            printf("%d %d\n",xx,yy);/*
            pii p = mp(xx,yy);
            int j;
            for (j = f.size()-1; j >= 0; j--) {
                if ((X[P] >= f[j].l) && (X[P] <= f[j].r) && (Y[P] >= f[j].d) && (Y[P] <= f[j].u)) {
                    int xx = X[P],yy = Y[P];
                    if (f[j].x != -1) xx = f[j].x;
                    if (f[j].y != -1) yy = f[j].y;
                    printf("o:%d %d\n",xx,yy);

                    assert(p == mp(xx,yy));
                    break;
                }
            }
            if (j < 0) printf("o:%d %d\n",X[P],Y[P]),assert(p == mp(X[P],Y[P]));*/
        }
        else if (T == 2) {
            L = l[i];
            ops.pb(mp(T,L));
            update(N-L,1,N+1);
        }
        else if (T == 3) {
            L = l[i];
            ops.pb(mp(T,L));
            update(L+1,2,N+1);
        }
        else {
            A = a[i],B = b[i];
            break;
        }
    }

    if (i < Q) {
        int pp = i;
        for (i = 0; i < ops.size(); i++) {
            int j;
            for (j = 0; j < M; j++) {
                if (ops[i].first == 2) {
                    if ((Y[j] <= ops[i].second) && (X[j] < N-ops[i].second)) X[j] = N-ops[i].second;
                }
                else {
                    if ((X[j] <= ops[i].second) && (Y[j] < N-ops[i].second)) Y[j] = N-ops[i].second;
                }
            }
        }
        X[M++] = A,Y[M-1] = B;
        for (i = pp+1; i < Q; i++) {
            T = t[i];
            if (T == 1) {
                P = p[i],P--;
                printf("%d %d\n",X[P],Y[P]);
            }
            else if (T == 2) {
                L = l[i];
                int j;
                for (j = 0; j < M; j++) {
                    if ((Y[j] <= L) && (X[j] < N-L)) X[j] = N-L;
                }
            }
            else if (T == 3) {
                L = l[i];
                int j;
                for (j = 0; j < M; j++) {
                    if ((X[j] <= L) && (Y[j] < N-L)) Y[j] = N-L;
                }
            }
            else {
                A = a[i],B = b[i];
                X[M++] = A,Y[M-1] = B;
            }
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sweeping.cpp: In function 'int main()':
sweeping.cpp:342:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < ops.size(); i++) {
                     ~~^~~~~~~~~~~~
sweeping.cpp:256:10: 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:257:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:259:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t[i]);
         ~~~~~^~~~~~~~~~~~
sweeping.cpp:260:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         if (t[i] == 1) scanf("%d",&p[i]);
                        ~~~~~^~~~~~~~~~~~
sweeping.cpp:261:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         else if (t[i] <= 3) scanf("%d",&l[i]);
                             ~~~~~^~~~~~~~~~~~
sweeping.cpp:262:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         else scanf("%d %d",&a[i],&b[i]);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~

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