Submission #231150

#	Time	Username	Problem	Language	Result	Execution time	Memory
231150		duality	Sweeping (JOI20_sweeping)	C++11	65 / 100	18059 ms	1423024 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[500000],Y[500000];
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 main() {
    int i;
    int N,M,Q;
    int T,P,L,A,B;
    scanf("%d %d %d",&N,&M,&Q);
    for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
    MM[0] = MM[N+1] = mp(0,0);
    root = new node;
    root->l = root->r = NULL;
    for (i = 0; i < Q; i++) {
        scanf("%d",&T);
        if (T == 1) {
            scanf("%d",&P),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) {
            scanf("%d",&L);
            ops.pb(mp(T,L));
            update(N-L,1,N+1);
        }
        else if (T == 3) {
            scanf("%d",&L);
            ops.pb(mp(T,L));
            update(L+1,2,N+1);
        }
        else {
            scanf("%d %d",&A,&B);
            break;
        }
    }

    if (i < Q) {
        int p = 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 = p+1; i < Q; i++) {
            scanf("%d",&T);
            if (T == 1) {
                scanf("%d",&P),P--;
                printf("%d %d\n",X[P],Y[P]);
            }
            else if (T == 2) {
                scanf("%d",&L);
                int j;
                for (j = 0; j < M; j++) {
                    if ((Y[j] <= L) && (X[j] < N-L)) X[j] = N-L;
                }
            }
            else if (T == 3) {
                scanf("%d",&L);
                int j;
                for (j = 0; j < M; j++) {
                    if ((X[j] <= L) && (Y[j] < N-L)) Y[j] = N-L;
                }
            }
            else {
                scanf("%d %d",&A,&B);
                X[M++] = A,Y[M-1] = B;
            }
        }
    }

    return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:269:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < ops.size(); i++) {
                     ~~^~~~~~~~~~~~
sweeping.cpp:222: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:223: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:228:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&T);
         ~~~~~^~~~~~~~~
sweeping.cpp:230:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&P),P--;
             ~~~~~~~~~~~~~~^~~~
sweeping.cpp:252:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:257:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:262:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&A,&B);
             ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:282:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&T);
             ~~~~~^~~~~~~~~
sweeping.cpp:284:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&P),P--;
                 ~~~~~~~~~~~~~~^~~~
sweeping.cpp:288:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&L);
                 ~~~~~^~~~~~~~~
sweeping.cpp:295:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&L);
                 ~~~~~^~~~~~~~~
sweeping.cpp:302:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d %d",&A,&B);
                 ~~~~~^~~~~~~~~~~~~~~

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