Submission #1049671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049671		phong	Golf (JOI17_golf)	C++17	0 / 100	134 ms	458064 KiB

golf

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
//#define int long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

struct node{
    int x1, x2, y1, y2;
}a[nmax];
int n, rt, S, T, U, V;
vector<int> nen;
int gg(int u){
    return lower_bound(nen.begin(), nen.end(), u) - nen.begin() + 1;
}
struct holder{
    int x, l, r;
     friend bool operator < (const holder &a, const holder&b){
        if(a.x == b.x){
            if(a.l == b.l) return a.r < b.r;
            return a.l < b.l;
        }
        return a.x < b.x;
    }
    friend bool operator == (const holder &a, const holder&b){
        return (a.x == b.x) && (a.l == b.l) &&(a.r == b.r);
    }
};

vector<holder> A, B;

int tree[nmax << 2], lz[nmax << 2];
void build(int idx){
    if(!idx) lz[1] = gg(-oo);
    else lz[1] = gg(oo);
}
void fix(int id, int val){
    if(!val) return;
    tree[id] = val;
    lz[id] = val;
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
    if(l > v || r < u || u > v) return;
    if(l >= u && r <= v) return fix(id, val);
    down(id);
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, v,val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
}
#define update(l, r, val) update(1, 1, rt, l, r, val)

int get(int id, int l, int r, int u){
    if(l == r) return tree[id];
    down(id);
    int mid = r + l >> 1;
    if(u <= mid)return get(id << 1, l, mid, u);
    return get(id << 1 | 1, mid + 1, r, u);
}
#define get(x) get(1, 1, rt, x)
int L[nmax], R[nmax];
void add(int x1, int y1, int x2, int y2){
    if(x1 > x2) swap(x1, x2);
    if(y1 > y2) swap(y1, y2);

    A.push_back({y1, x1, x2});
    A.push_back({y2, x1, x2});
    B.push_back({x1, y1, y2});
    B.push_back({x2, y1, y2});
}
struct hos{
    int x, l, r, id;
};
vector<holder> one,two;
vector<int> adj[nmax];
//A doc
//B ngang

int ans[nmax][2];
deque<pii> q;
struct clgt{
    int first, second, id;
    friend bool operator < (const clgt &a, const clgt&b){
        if(a.fi == b.fi){
            if(a.se == b.se) return a.id < b.id;
            return a.se < b.se;
        }
        return a.fi < b.fi;
    }
    friend bool operator == (const clgt &a, const clgt&b){
        return (a.fi == b.fi) && (a.se == b.se) &&(a.id == b.id);
    }
};
vector<clgt> ola;
struct concac{
//
    set<clgt> tree[nmax << 2];
    void Update(int id, int l, int r, int u, clgt tmp, int idx){
        if(l > u || r < u) return;
        if(l == r){
            if(idx) tree[id].insert(tmp);
            else tree[id].erase(tmp);
            return;
        }
        int mid = r + l >> 1;
        Update(id << 1, l, mid, u, tmp, idx);
        Update(id << 1 | 1, mid + 1, r, u, tmp, idx);
        if(idx) tree[id].insert(tmp);
        else tree[id].erase(tmp);
    }
    void Find(int id, int l, int r, int u, int v, int x){
        if(l > v ||r < u) return;
        if(l >= u && r <= v){
            auto it = tree[id].lower_bound({x, -oo,-oo});
            while(it !=tree[id].end()){
                if(it->se <= x){
                    ola.push_back({it->se, it->fi, it->id});
                    return;
                }
                ++it;
            }
            return;
        }
        int mid = r + l >> 1;
        Find(id << 1, l, mid, u, v, x);
        Find(id << 1 | 1, mid + 1, r, u, v, x);
    }
}FF[2];
map<int,int> mp[nmax];
void solve(){
    //tao canh
    S = gg(S), T = gg(T);
    U = gg(U), V = gg(V);
//    cout << nen[U - 1]<< ' ' << nen[V - 1] << ' ';
    add(gg(-oo), gg(-oo), gg(oo), gg(oo));
    for(int i = 1; i <= n; ++i){
        A.push_back({a[i].y1, a[i].x1 + 1, a[i].x2 - 1});
        A.push_back({a[i].y2, a[i].x1 + 1, a[i].x2 - 1});
        B.push_back({a[i].x1, a[i].y1 + 1, a[i].y2 - 1});
        B.push_back({a[i].x2, a[i].y1 + 1, a[i].y2 - 1});
    }
    one.push_back({gg(-oo), gg(-oo), gg(oo)});
    one.push_back({gg(oo), gg(-oo), gg(oo)});
    two.push_back({gg(-oo), gg(-oo), gg(oo)});
    two.push_back({gg(oo), gg(-oo), gg(oo)});
    sort(A.begin(), A.end(), [](holder A, holder B){
        return A.x < B.x;
         });
    vector<pii> tmp;
    tmp.push_back({S, T});
    tmp.push_back({U, V});
    for(int i = 1; i <= n; ++i){
        tmp.push_back({a[i].x1, a[i].y1});
        tmp.push_back({a[i].x1, a[i].y2});
        tmp.push_back({a[i].x2, a[i].y1});
        tmp.push_back({a[i].x2, a[i].y2});
    }
    //#####
    sort(tmp.begin(), tmp.end(), [](pii a, pii b){
         return a.se < b.se;
         });
    build(0);
    int pos = 0;
    for(int i = 0; i < tmp.size(); ++i){
        int x = tmp[i].fi, y = tmp[i].se;
        while(pos < A.size() && A[pos].x < y){
            update(A[pos].l, A[pos].r, A[pos].x);
            ++pos;
        }
        L[i] = get(x);
    }
    build(1);
    pos = 0;
    reverse(A.begin(), A.end());
    for(int i = tmp.size() - 1; i >= 0; --i){
        int x = tmp[i].fi, y = tmp[i].se;
        while(pos < A.size() && A[pos].x > y){
            update(A[pos].l, A[pos].r, A[pos].x);
            ++pos;
        }
        R[i] = get(x);
    }
    for(int i = 0; i < tmp.size(); ++i){
        one.push_back({tmp[i].fi, L[i], R[i]});

    }
    //######
    sort(B.begin(), B.end(), [](holder A, holder B){
        return A.x < B.x;
         });
     sort(tmp.begin(), tmp.end(), [](pii a, pii b){
         return a.fi < b.fi;
         });
    build(0); pos = 0;
    for(int i = 0; i < tmp.size(); ++i){
        int x = tmp[i].fi, y = tmp[i].se;
        while(pos < B.size() && B[pos].x < x){
            update(B[pos].l, B[pos].r, B[pos].x);
            ++pos;
        }
        L[i] = get(y);
    }
    build(1); pos = 0;
    reverse(B.begin(), B.end());
    for(int i = tmp.size() - 1; i >= 0; --i){
        int x = tmp[i].fi, y = tmp[i].se;
        while(pos < B.size() && B[pos].x > x){
            update(B[pos].l, B[pos].r, B[pos].x);
            ++pos;
        }
        R[i] = get(y);
    }
    for(int i = 0; i < tmp.size(); ++i){
        two.push_back({tmp[i].se, L[i], R[i]});
    }
    sort(one.begin(), one.end());
    one.erase(unique(one.begin(), one.end()), one.end());
    sort(two.begin(), two.end());
    two.erase(unique(two.begin(), two.end()), two.end());
    //#####
    memset(ans, 0x3f, sizeof ans);
    for(int i =0; i < one.size(); ++i){
        int x = one[i].x, l =one[i].l, r = one[i].r;

        FF[0].Update(1, 1, nen.size(), x, {r, l, i}, 1);
    }
   for(int i =0; i < two.size(); ++i){
        int x = two[i].x, l =two[i].l, r = two[i].r;
        FF[1].Update(1, 1, nen.size(), x, {r, l, i}, 1);
    }
    for(int i = 0; i < one.size(); ++i){
        if(S == one[i].x && one[i].l <= T && one[i].r >= T ){
            q.push_back({i, 0});
            ans[i][0] = 1;
            FF[0].Update(1, 1, nen.size(), one[i].x, {one[i].r,  one[i].l, i}, 0);

        }

    }
    for(int i = 0; i < two.size(); ++i){
        if(T == two[i].x && two[i].l <= S && two[i].r >= S){
            q.push_back({i, 1});
            ans[i][1] = 1;
            FF[1].Update(1, 1, nen.size(), two[i].x, {two[i].r,  two[i].l, i}, 0);
        }
//        cout << two[i].x << ' ' << two[i].l << ' ' << two[i].r << endl;
    }
    while(q.size()){
        pii tmp = q.front(); q.pop_front();
        if(tmp.se == 0){
            int x = one[tmp.fi].x, l = one[tmp.fi].l, r = one[tmp.fi].r;
            while(1){
                FF[1].Find(1, 1, nen.size(), l, r, x);
                if(ola.empty())break;
                for(auto p : ola){
                    int j = p.id;
                    int y = two[j].x, le = two[j].l, ri = two[j].r;
                    if(le <= x && x <= ri && l <= y && y <= r){
                        if(U == y && le <= V && ri >= V){
                            cout << ans[tmp.fi][0] + 1;
                            exit(0);
                        }
                        if(ans[j][1] > oo){
                            ans[j][1] = ans[tmp.fi][0] + 1;
                            q.push_back({j, 1});
                        }
                    }
                    FF[1].Update(1, 1, nen.size(), y, {ri, le, j}, 0);
                }
                ola.clear();
            }
        }
        else{
            int x = two[tmp.fi].x, l = two[tmp.fi].l, r = two[tmp.fi].r;
//            cout << nen[x - 1] << endl;
            while(1){
                FF[0].Find(1, 1, nen.size(), l, r, x);
                if(ola.empty()) break;
                for(auto p : ola){
                    int j = p.id;
                    int y = one[j].x, le = one[j].l, ri = one[j].r;
//                    cout << nen[y - 1] << ' ' << nen[le - 1] << ' ' << nen[ri - 1] << endl;;
                    if(le <= x && x <= ri && l <= y && y <= r){
                        if(U == y && le <= V && ri >= V){
                            cout << ans[tmp.fi][1] + 1;
                            exit(0);
                        }
                        if(ans[j][0] > oo){
                            ans[j][0] = ans[tmp.fi][1] + 1;
                            q.push_back({j, 0});
                        }
                    }
                    FF[0].Update(1, 1, nen.size(), y, {ri, le, j}, 0);
                }
                ola.clear();
            }
//            exit(0);
        }
        ola.clear();
    }
//    int mi = oo;
//    for(int i = 0; i < one.size(); ++i){
//        if(U == one[i].x && one[i].l <= V && one[i].r >= V ){
//            mi = min(ans[i][0], mi);
//        }
////        cout << nen[one[i].x - 1]<< ' ' << nen[one[i].l - 1] << ' ' << nen[one[i].r - 1] << ' ' << ans[i][0] << endl;
//
//    }
//    for(int i = 0; i < two.size(); ++i){
//        if(V == two[i].x && two[i].l <= U && two[i].r >= U){
//            mi = min(mi, ans[i][1]);
//        }
////        cout << nen[two[i].x - 1] << ' ' << nen[two[i].l - 1] << ' ' << nen[two[i].r - 1] << ' ' << ans[i][1] << endl;
//
//    }
//    cout << mi;
}
int vis[200][200];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> S >> T >> U >> V >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].x1 >> a[i].x2 >> a[i].y1 >> a[i].y2;
        nen.push_back(a[i].x1);
        nen.push_back(a[i].x2);
        nen.push_back(a[i].y1);
        nen.push_back(a[i].y2);
        nen.push_back(a[i].x1 - 1);
        nen.push_back(a[i].x2 + 1);
        nen.push_back(a[i].y1 - 1);
        nen.push_back(a[i].y2 + 1);
    }
//    for(int i = 1; i <= n; ++i){
//        for(int x = a[i].x1; x <= a[i].x2; ++x){
//            for(int y= a[i].y1; y <= a[i].y2;++y)vis[x][y] = i;
//        }
//    }
//        vis[S][T] = vis[U][V]= 9;
//    for(int i = 0; i <= 30; ++i){
//        for(int j = 0; j <= 30; ++j){
////            if(vis[i][j] == 1) cout << "#";
////            else if(vis[i][j] == 2) cout << "?";
////            else cout << ".";
//            cout << vis[i][j];
//        }
//        cout << endl;
//    }
    for(int x = -1; x <= 1; ++x){
        nen.push_back(S + x);    nen.push_back(U + x);
        nen.push_back(T + x);    nen.push_back(V + x);
        nen.push_back(-oo + x);  nen.push_back(oo + x);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    rt = nen.size();
    for(int i = 1; i <= n; ++i){
        a[i].x1 = gg(a[i].x1);
        a[i].x2 = gg(a[i].x2);
        a[i].y1 = gg(a[i].y1);
        a[i].y2 = gg(a[i].y2);
    }
    //tao canh
    solve();
}
/*
-1000000005 -1000000005 1000000005
1 -1000000005 1000000005
6 -1000000005 1000000005
1000000005 -1000000005 1000000005
4 -1000000005 1000000005
9 4 23 9
5
12 27 14 30
8 19 8 9
6 21 5 7
1 4 4 29
11 20 11 12

*/

Compilation message (stderr)

golf.cpp: In function 'void update(int, int, int, int, int, int)':
golf.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = r + l >> 1;
      |               ~~^~~
golf.cpp: In function 'int get(int, int, int, int)':
golf.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = r + l >> 1;
      |               ~~^~~
golf.cpp: In member function 'void concac::Update(int, int, int, int, clgt, int)':
golf.cpp:119:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid = r + l >> 1;
      |                   ~~^~~
golf.cpp: In member function 'void concac::Find(int, int, int, int, int, int)':
golf.cpp:138:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int mid = r + l >> 1;
      |                   ~~^~~
golf.cpp: In function 'void solve()':
golf.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:180:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         while(pos < A.size() && A[pos].x < y){
      |               ~~~~^~~~~~~~~~
golf.cpp:191:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         while(pos < A.size() && A[pos].x > y){
      |               ~~~~^~~~~~~~~~
golf.cpp:197:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:209:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:211:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         while(pos < B.size() && B[pos].x < x){
      |               ~~~~^~~~~~~~~~
golf.cpp:221:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |         while(pos < B.size() && B[pos].x > x){
      |               ~~~~^~~~~~~~~~
golf.cpp:227:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:236:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for(int i =0; i < one.size(); ++i){
      |                   ~~^~~~~~~~~~~~
golf.cpp:241:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |    for(int i =0; i < two.size(); ++i){
      |                  ~~^~~~~~~~~~~~
golf.cpp:245:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     for(int i = 0; i < one.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:254:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |     for(int i = 0; i < two.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp: At global scope:
golf.cpp:333:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  333 | main(){
      | ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70