oj.uz

Submission #231150

# Submission time Handle Problem Language Result Execution time Memory
231150 2020-05-12T22:08:06 Z duality Sweeping (JOI20_sweeping) C++11
65 / 100
 18000 ms 1423024 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 29 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18059 ms 14972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12796 ms 1390828 KB Output is correct
2 Correct 7910 ms 1344032 KB Output is correct
3 Correct 8347 ms 1423024 KB Output is correct
4 Correct 9015 ms 1237484 KB Output is correct
5 Correct 5512 ms 1122796 KB Output is correct
6 Correct 7842 ms 1261768 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 12796 ms 1390828 KB Output is correct
2 Correct 7910 ms 1344032 KB Output is correct
3 Correct 8347 ms 1423024 KB Output is correct
4 Correct 9015 ms 1237484 KB Output is correct
5 Correct 5512 ms 1122796 KB Output is correct
6 Correct 7842 ms 1261768 KB Output is correct
7 Correct 8028 ms 1339944 KB Output is correct
8 Correct 8466 ms 1345964 KB Output is correct
9 Correct 8039 ms 1342088 KB Output is correct
10 Correct 8592 ms 1422528 KB Output is correct
11 Correct 9056 ms 1236128 KB Output is correct
12 Correct 7881 ms 1260448 KB Output is correct
13 Correct 7786 ms 1234476 KB Output is correct
14 Correct 240 ms 12240 KB Output is correct
15 Correct 647 ms 29944 KB Output is correct
16 Correct 13265 ms 1338736 KB Output is correct
17 Correct 7828 ms 1260580 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 29 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Execution timed out 18059 ms 14972 KB Time limit exceeded
8 Halted 0 ms 0 KB -