oj.uz

Submission #1049219

# Submission time Handle Problem Language Result Execution time Memory
1049219 2024-08-08T15:07:27 Z phong Golf (JOI17_golf) C++17
30 / 100
 10000 ms 85480 KB 
//#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;
};

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;
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]});
    }

    //#####
    memset(ans, 0x3f, sizeof ans);
    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;
        }
    }
    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;
        }
    }
    while(q.size()){
        pii tmp = q.front();q.pop_front();
        if(tmp.se == 0){
            for(int j = 0; j < two.size(); ++j){
                int x = one[tmp.fi].x, l = one[tmp.fi].l, r = one[tmp.fi].r;
                int y = two[j].x, le = two[j].l, ri = two[j].r;
                if(le <= x && x <= ri && l <= y && y <= r){
                    if(ans[j][1] > oo){
                        ans[j][1] = ans[tmp.fi][0] + 1;
                        q.push_back({j, 1});
                    }
                }
            }
        }
        else{

            for(int j = 0; j < one.size(); ++j){
                int x = two[tmp.fi].x, l = two[tmp.fi].l, r = two[tmp.fi].r;
                int y = one[j].x, le = one[j].l, ri = one[j].r;
                if(le <= x && x <= ri && l <= y && y <= r){
                    if(ans[j][0] > oo){
                        ans[j][0] = ans[tmp.fi][1] + 1;
                        q.push_back({j, 0});
                    }
                }
            }
        }
    }
    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;

    }
//    cout <<"###\n";
    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;
}
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 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);
    }
//    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] = 1;
//            }
//        }
//    }
//    vis[S][T] = vis[U][V]= 2;
//    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 << endl;
//    }
    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();
}
/*
0 0 5 5
1
2 3 2 4

3 5 8 6
1
5 6 2 8
*/

Compilation message

golf.cpp: In function 'void update(int, int, int, int, int, int)':
golf.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = r + l >> 1;
      |               ~~^~~
golf.cpp: In function 'int get(int, int, int, int)':
golf.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = r + l >> 1;
      |               ~~^~~
golf.cpp: In function 'void solve()':
golf.cpp:119: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]
  119 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while(pos < A.size() && A[pos].x < y){
      |               ~~~~^~~~~~~~~~
golf.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         while(pos < A.size() && A[pos].x > y){
      |               ~~~~^~~~~~~~~~
golf.cpp:138: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]
  138 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:150: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]
  150 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         while(pos < B.size() && B[pos].x < x){
      |               ~~~~^~~~~~~~~~
golf.cpp:162:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         while(pos < B.size() && B[pos].x > x){
      |               ~~~~^~~~~~~~~~
golf.cpp:168: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]
  168 |     for(int i = 0; i < tmp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for(int i = 0; i < one.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:180:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for(int i = 0; i < two.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:189:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |             for(int j = 0; j < two.size(); ++j){
      |                            ~~^~~~~~~~~~~~
golf.cpp:202:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |             for(int j = 0; j < one.size(); ++j){
      |                            ~~^~~~~~~~~~~~
golf.cpp:215:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     for(int i = 0; i < one.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i = 0; i < two.size(); ++i){
      |                    ~~^~~~~~~~~~~~
golf.cpp: At global scope:
golf.cpp:232:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  232 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41560 KB Output is correct
2 Correct 5 ms 41564 KB Output is correct
3 Correct 5 ms 41560 KB Output is correct
4 Correct 9 ms 41564 KB Output is correct
5 Correct 58 ms 41940 KB Output is correct
6 Correct 56 ms 41936 KB Output is correct
7 Correct 67 ms 41936 KB Output is correct
8 Correct 94 ms 41936 KB Output is correct
9 Correct 57 ms 41820 KB Output is correct
10 Correct 80 ms 41816 KB Output is correct
11 Correct 64 ms 41932 KB Output is correct
12 Correct 57 ms 41820 KB Output is correct
13 Correct 56 ms 41820 KB Output is correct
14 Correct 90 ms 41880 KB Output is correct
15 Correct 13 ms 41564 KB Output is correct
16 Correct 51 ms 41924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41560 KB Output is correct
2 Correct 5 ms 41564 KB Output is correct
3 Correct 5 ms 41560 KB Output is correct
4 Correct 9 ms 41564 KB Output is correct
5 Correct 58 ms 41940 KB Output is correct
6 Correct 56 ms 41936 KB Output is correct
7 Correct 67 ms 41936 KB Output is correct
8 Correct 94 ms 41936 KB Output is correct
9 Correct 57 ms 41820 KB Output is correct
10 Correct 80 ms 41816 KB Output is correct
11 Correct 64 ms 41932 KB Output is correct
12 Correct 57 ms 41820 KB Output is correct
13 Correct 56 ms 41820 KB Output is correct
14 Correct 90 ms 41880 KB Output is correct
15 Correct 13 ms 41564 KB Output is correct
16 Correct 51 ms 41924 KB Output is correct
17 Correct 56 ms 43864 KB Output is correct
18 Correct 73 ms 43816 KB Output is correct
19 Correct 53 ms 43868 KB Output is correct
20 Correct 55 ms 43864 KB Output is correct
21 Correct 55 ms 44120 KB Output is correct
22 Correct 105 ms 43868 KB Output is correct
23 Correct 65 ms 44008 KB Output is correct
24 Correct 57 ms 44012 KB Output is correct
25 Correct 66 ms 43864 KB Output is correct
26 Correct 87 ms 43868 KB Output is correct
27 Correct 27 ms 41816 KB Output is correct
28 Correct 42 ms 41820 KB Output is correct
29 Correct 43 ms 41820 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41560 KB Output is correct
2 Correct 5 ms 41564 KB Output is correct
3 Correct 5 ms 41560 KB Output is correct
4 Correct 9 ms 41564 KB Output is correct
5 Correct 58 ms 41940 KB Output is correct
6 Correct 56 ms 41936 KB Output is correct
7 Correct 67 ms 41936 KB Output is correct
8 Correct 94 ms 41936 KB Output is correct
9 Correct 57 ms 41820 KB Output is correct
10 Correct 80 ms 41816 KB Output is correct
11 Correct 64 ms 41932 KB Output is correct
12 Correct 57 ms 41820 KB Output is correct
13 Correct 56 ms 41820 KB Output is correct
14 Correct 90 ms 41880 KB Output is correct
15 Correct 13 ms 41564 KB Output is correct
16 Correct 51 ms 41924 KB Output is correct
17 Correct 56 ms 43864 KB Output is correct
18 Correct 73 ms 43816 KB Output is correct
19 Correct 53 ms 43868 KB Output is correct
20 Correct 55 ms 43864 KB Output is correct
21 Correct 55 ms 44120 KB Output is correct
22 Correct 105 ms 43868 KB Output is correct
23 Correct 65 ms 44008 KB Output is correct
24 Correct 57 ms 44012 KB Output is correct
25 Correct 66 ms 43864 KB Output is correct
26 Correct 87 ms 43868 KB Output is correct
27 Correct 27 ms 41816 KB Output is correct
28 Correct 42 ms 41820 KB Output is correct
29 Correct 43 ms 41820 KB Output is correct
30 Execution timed out 10066 ms 85480 KB Time limit exceeded
31 Halted 0 ms 0 KB -