제출 #232078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232078		duality	청소 (JOI20_sweeping)	C++11	100 / 100	12627 ms	249792 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 ----------

int X[1500000],Y[1500000],A[1500000];
vpii updates,queries;
pii ans[1500000];
class comp1 {
    public:
        bool operator()(int a,int b) {
            if (ans[a].first == ans[b].first) return a < b;
            else return ans[a].first < ans[b].first;
        }
};
class comp2 {
    public:
        bool operator()(int a,int b) {
            if (ans[a].second == ans[b].second) return a < b;
            else return ans[a].second < ans[b].second;
        }
};
set<int,comp1> S1[1500000];
set<int,comp2> S2[1500000];
map<int,int> MM;
int findAns(int l,int r,vi q,int N) {
    if (q.empty()) return 0;
    int i;
    vi c;
    for (i = 0; i < q.size(); i++) {
        int s = A[queries[q[i]].first],e = queries[q[i]].second;
        if ((e < l) || (s > r)) continue;
        if ((l >= s) && (r <= e)) S1[0].insert(q[i]),S2[0].insert(q[i]);
        else c.pb(q[i]);
    }
    if (!S1[0].empty()) {
        MM[0] = 0,MM[N] = -1;
        int x = 1;
        for (i = l; i <= r; i++) {
            if (MM.count(updates[i].second)) continue;
            int u = (--MM.lower_bound(updates[i].second))->second;
            MM[updates[i].second] = x++;
            if (updates[i].first == 1) {
                auto it = S2[u].begin(),it2 = S2[u].end();
                int f = -1;
                while (1) {
                    if ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) it++;
                    else {
                        f = 0;
                        break;
                    }
                    if ((it2 == S2[u].begin()) || (ans[*(--it2)].second < N-updates[i].second)) {
                        f = 1;
                        break;
                    }
                }
                if (f) {
                    swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]);
                    it2 = S2[x-1].end();
                    while ((it2 != S2[x-1].begin()) && (ans[*(--it2)].second >= N-updates[i].second)) {
                        S1[u].insert(*it2),S2[u].insert(*it2);
                        S1[x-1].erase(*it2),it2 = S2[x-1].erase(it2);
                    }
                }
                else {
                    it = S2[u].begin();
                    while ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) {
                        S1[x-1].insert(*it),S2[x-1].insert(*it);
                        S1[u].erase(*it),it = S2[u].erase(it);
                    }
                }
            }
            else {
                auto it = S1[u].begin(),it2 = S1[u].end();
                int f = -1;
                while (1) {
                    if ((it != S1[u].end()) && (ans[*it].first < updates[i].second)) it++;
                    else {
                        f = 0;
                        break;
                    }
                    if ((it2 == S1[u].begin()) || (ans[*(--it2)].first < updates[i].second)) {
                        f = 1;
                        break;
                    }
                }
                if (f) {
                    it2 = S1[u].end();
                    while ((it2 != S1[u].begin()) && (ans[*(--it2)].first >= updates[i].second)) {
                        S1[x-1].insert(*it2),S2[x-1].insert(*it2);
                        S2[u].erase(*it2),it2 = S1[u].erase(it2);
                    }
                }
                else {
                    swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]);
                    it = S1[x-1].begin();
                    while ((it != S1[x-1].end()) && (ans[*it].first < updates[i].second)) {
                        S1[u].insert(*it),S2[u].insert(*it);
                        S2[x-1].erase(*it),it = S1[x-1].erase(it);
                    }
                }
            }
        }
        for (auto it = MM.begin(); it->second != -1; it++) {
            auto it2 = it;
            it2++;
            int x1 = it->first,x2 = it2->first;
            for (auto it3 = S1[it->second].begin(); it3 != S1[it->second].end(); it3++) {
                ans[*it3].first = max(ans[*it3].first,x1);
                ans[*it3].second = max(ans[*it3].second,N-x2);
            }
            S1[it->second].clear(),S2[it->second].clear();
        }
        MM.clear();
    }
    if (l != r) {
        int m = (l+r) / 2;
        findAns(l,m,c,N),findAns(m+1,r,c,N);
    }
    return 0;
}
int main() {
    int i;
    int N,M,Q;
    int T,P,L;
    scanf("%d %d %d",&N,&M,&Q);
    for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]),A[i] = 0;
    for (i = 0; i < Q; i++) {
        scanf("%d",&T);
        if (T == 1) {
            scanf("%d",&P),P--;
            queries.pb(mp(P,(int) updates.size()-1));
        }
        else if (T == 2) {
            scanf("%d",&L);
            updates.pb(mp(1,N-L));
        }
        else if (T == 3) {
            scanf("%d",&L);
            updates.pb(mp(2,L+1));
        }
        else {
            scanf("%d %d",&X[M],&Y[M]);
            A[M++] = updates.size();
        }
    }
    vi q;
    for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i);
    findAns(0,(int) updates.size()-1,q,N+1);
    for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second);

    return 0;
}

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

sweeping.cpp: In function 'int findAns(int, int, vi, int)':
sweeping.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < q.size(); i++) {
                 ~~^~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:200:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i);
                 ~~^~~~~~~~~~~~~~~~
sweeping.cpp:202:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second);
                 ~~^~~~~~~~~~~~~~~~
sweeping.cpp:178: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:179:55: 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]),A[i] = 0;
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
sweeping.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&T);
         ~~~~~^~~~~~~~~
sweeping.cpp:183:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&P),P--;
             ~~~~~~~~~~~~~~^~~~
sweeping.cpp:187:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:195:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&X[M],&Y[M]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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