oj.uz

Submission #231153

# Submission time Handle Problem Language Result Execution time Memory
231153 2020-05-12T22:22:06 Z duality Sweeping (JOI20_sweeping) C++11
75 / 100
 18000 ms 1449336 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[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;
}

Compilation message

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2216 ms 66768 KB Output is correct
2 Correct 2195 ms 76796 KB Output is correct
3 Correct 2207 ms 76760 KB Output is correct
4 Correct 2008 ms 75644 KB Output is correct
5 Correct 1979 ms 76112 KB Output is correct
6 Correct 2137 ms 65104 KB Output is correct
7 Correct 2264 ms 76768 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12849 ms 1401092 KB Output is correct
2 Correct 7847 ms 1371640 KB Output is correct
3 Correct 8298 ms 1449336 KB Output is correct
4 Correct 9128 ms 1265236 KB Output is correct
5 Correct 5484 ms 1150320 KB Output is correct
6 Correct 7788 ms 1289328 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 12849 ms 1401092 KB Output is correct
2 Correct 7847 ms 1371640 KB Output is correct
3 Correct 8298 ms 1449336 KB Output is correct
4 Correct 9128 ms 1265236 KB Output is correct
5 Correct 5484 ms 1150320 KB Output is correct
6 Correct 7788 ms 1289328 KB Output is correct
7 Correct 7923 ms 1368196 KB Output is correct
8 Correct 8117 ms 1373392 KB Output is correct
9 Correct 8007 ms 1369868 KB Output is correct
10 Correct 8393 ms 1449212 KB Output is correct
11 Correct 9087 ms 1266308 KB Output is correct
12 Correct 7839 ms 1291076 KB Output is correct
13 Correct 7723 ms 1264876 KB Output is correct
14 Correct 236 ms 16996 KB Output is correct
15 Correct 2123 ms 36572 KB Output is correct
16 Correct 13219 ms 1369156 KB Output is correct
17 Correct 7787 ms 1288128 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 512 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 29 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 2216 ms 66768 KB Output is correct
8 Correct 2195 ms 76796 KB Output is correct
9 Correct 2207 ms 76760 KB Output is correct
10 Correct 2008 ms 75644 KB Output is correct
11 Correct 1979 ms 76112 KB Output is correct
12 Correct 2137 ms 65104 KB Output is correct
13 Correct 2264 ms 76768 KB Output is correct
14 Correct 12849 ms 1401092 KB Output is correct
15 Correct 7847 ms 1371640 KB Output is correct
16 Correct 8298 ms 1449336 KB Output is correct
17 Correct 9128 ms 1265236 KB Output is correct
18 Correct 5484 ms 1150320 KB Output is correct
19 Correct 7788 ms 1289328 KB Output is correct
20 Correct 7923 ms 1368196 KB Output is correct
21 Correct 8117 ms 1373392 KB Output is correct
22 Correct 8007 ms 1369868 KB Output is correct
23 Correct 8393 ms 1449212 KB Output is correct
24 Correct 9087 ms 1266308 KB Output is correct
25 Correct 7839 ms 1291076 KB Output is correct
26 Correct 7723 ms 1264876 KB Output is correct
27 Correct 236 ms 16996 KB Output is correct
28 Correct 2123 ms 36572 KB Output is correct
29 Correct 13219 ms 1369156 KB Output is correct
30 Correct 7787 ms 1288128 KB Output is correct
31 Execution timed out 18047 ms 45276 KB Time limit exceeded
32 Halted 0 ms 0 KB -