oj.uz

Submission #398226

# Submission time Handle Problem Language Result Execution time Memory
398226 2021-05-04T01:10:22 Z duality Golf (JOI17_golf) C++11
100 / 100
 2731 ms 340936 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 ----------

int A[100000],B[100000],C[100000],D[100000];
struct seg { int z,l,r; };
vector<seg> hor,ver;
struct seg2 { int z,l,r,t; };
bool comp(seg2 a,seg2 b) {
    if (a.z == b.z) return a.t < b.t;
    else return a.z < b.z;
}
vector<seg2> events;
set<pii> SS;
vi vv;
vpii events2;
vpii tree[1 << 19];
int update(int s,int e,int ai,int i,int t,int u) {
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        tree[i].pb(mp(t,u));
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,ai,2*i+1,t,u),update(mid+1,e,ai,2*i+2,t,u);
    tree[i].pb(mp(t,u));
    return 0;
}
int add(int s,int e,int as,int ae,int i,int u) {
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        tree[i].pb(mp(0,u));
        return 0;
    }

    int mid = (s+e) / 2;
    add(s,mid,as,ae,2*i+1,u),add(mid+1,e,as,ae,2*i+2,u);
    return 0;
}
vi adjList[5000000];
int num;
int pos[400004];
vi tree2[1 << 19];
int node[1 << 19],node2[1 << 19];
int update2(int s,int e,int as,int ae,int i,int u) {
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        tree2[i].pb(u);
        return 0;
    }

    int mid = (s+e) / 2;
    update2(s,mid,as,ae,2*i+1,u),update2(mid+1,e,as,ae,2*i+2,u);
    return 0;
}
int build(int s,int e,int i) {
    if (s == e) {
        if (!tree2[i].empty()) {
            int j;
            node[i] = num++,node2[i] = num++;
            for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
        }
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    if (!tree2[i].empty()) {
        int j;
        node[i] = num++,node2[i] = num++;
        for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
    }
    return 0;
}
int add2(int s,int e,int ai,int i,int u) {
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        if (!tree2[i].empty()) adjList[u].pb(node[i]),adjList[node2[i]].pb(u);
        return 0;
    }

    int mid = (s+e) / 2;
    add2(s,mid,ai,2*i+1,u),add2(mid+1,e,ai,2*i+2,u);
    if (!tree2[i].empty()) adjList[u].pb(node[i]),adjList[node2[i]].pb(u);
    return 0;
}
int clear(int s,int e,int i) {
    if (s == e) {
        tree2[i].clear();
        return 0;
    }

    int mid = (s+e) / 2;
    clear(s,mid,2*i+1),clear(mid+1,e,2*i+2);
    tree2[i].clear();
    return 0;
}
int process(vpii &v) {
    int i,c = 0,d = 0;
    for (i = 0; i < v.size(); i++) c += v[i].first == 0;
    if (c == 0) {
        v.clear();
        return 0;
    }
    for (i = 0; i < v.size(); i++) {
        if (v[i].first == 1) pos[v[i].second] = d;
        else if (v[i].first == -1) update2(0,c-1,pos[v[i].second],d-1,0,v[i].second);
        else d++;
    }
    d = 0;
    build(0,c-1,0);
    for (i = 0; i < v.size(); i++) {
        if (v[i].first == 0) add2(0,c-1,d++,0,v[i].second);
    }
    clear(0,c-1,0),v.clear();
    return 0;
}
int process(int s,int e,int i) {
    if (s == e) {
        process(tree[i]);
        return 0;
    }

    int mid = (s+e) / 2;
    process(s,mid,2*i+1),process(mid+1,e,2*i+2);
    process(tree[i]);
    return 0;
}
int dist[5000000];
queue<int> Q;
int main() {
    int i;
    int N,S,T,U,V;
    scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
    for (i = 0; i < N; i++) scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);

    for (i = 0; i < N; i++) {
        events.pb((seg2){C[i],A[i],B[i],1});
        events.pb((seg2){D[i],A[i],B[i],-1});
    }
    events.pb((seg2){T,S,S,0});
    events.pb((seg2){V,U,U,0});
    sort(events.begin(),events.end(),comp);
    SS.insert(mp(2e9,2e9));
    SS.insert(mp(-2e9,-2e9));
    for (i = 0; i < events.size(); i++) {
        if (events[i].t == -1) SS.erase(mp(events[i].l,events[i].r));
        auto it = SS.lower_bound(mp(events[i].l,0));
        auto it2 = it;
        it--;
        hor.pb((seg){events[i].z,it->second,it2->first}),vv.pb(events[i].z);
        if (events[i].t == 1) SS.insert(mp(events[i].l,events[i].r));
    }
    events.clear();
    for (i = 0; i < N; i++) {
        events.pb((seg2){A[i],C[i],D[i],1});
        events.pb((seg2){B[i],C[i],D[i],-1});
    }
    events.pb((seg2){S,T,T,0});
    events.pb((seg2){U,V,V,0});
    sort(events.begin(),events.end(),comp);
    for (i = 0; i < events.size(); i++) {
        if (events[i].t == -1) SS.erase(mp(events[i].l,events[i].r));
        auto it = SS.lower_bound(mp(events[i].l,0));
        auto it2 = it;
        it--;
        ver.pb((seg){events[i].z,it->second,it2->first});
        if (events[i].t == 1) SS.insert(mp(events[i].l,events[i].r));
    }

    sort(vv.begin(),vv.end());
    vv.resize(unique(vv.begin(),vv.end())-vv.begin());
    for (i = 0; i < hor.size(); i++) events2.pb(mp(hor[i].l,-(i+ver.size()+1))),events2.pb(mp(hor[i].r,i+ver.size()+1));
    for (i = 0; i < ver.size(); i++) events2.pb(mp(ver[i].z,-(i+1)));
    sort(events2.begin(),events2.end());
    for (i = 0; i < events2.size(); i++) {
        if (events2[i].second < -(int) ver.size()) {
            int u = -events2[i].second-1;
            int p = lower_bound(vv.begin(),vv.end(),hor[u-ver.size()].z)-vv.begin();
            update(0,vv.size()-1,p,0,1,u);
        }
        else if (events2[i].second < 0) {
            int u = -events2[i].second-1;
            int p = lower_bound(vv.begin(),vv.end(),ver[u].l)-vv.begin();
            int q = upper_bound(vv.begin(),vv.end(),ver[u].r)-vv.begin()-1;
            add(0,vv.size()-1,p,q,0,u);
        }
        else {
            int u = events2[i].second-1;
            int p = lower_bound(vv.begin(),vv.end(),hor[u-ver.size()].z)-vv.begin();
            update(0,vv.size()-1,p,0,-1,u);
        }
    }
    num = hor.size()+ver.size();
    process(0,vv.size()-1,0);

    for (i = 0; i < num; i++) dist[i] = -1;
    for (i = 0; i < ver.size(); i++) {
        if ((ver[i].z == S) && (ver[i].l <= T) && (ver[i].r >= T)) dist[i] = 0,Q.push(i);
    }
    for (i = 0; i < hor.size(); i++) {
        if ((hor[i].z == T) && (hor[i].l <= S) && (hor[i].r >= S)) dist[i+ver.size()] = 0,Q.push(i+ver.size());
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();

        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i];
            if (dist[v] == -1) dist[v] = dist[u]+1,Q.push(v);
        }
    }
    int ans = 1e9;
    for (i = 0; i < ver.size(); i++) {
        if ((ver[i].z == U) && (ver[i].l <= V) && (ver[i].r >= V)) ans = min(ans,dist[i]);
    }
    for (i = 0; i < hor.size(); i++) {
        if ((hor[i].z == V) && (hor[i].l <= U) && (hor[i].r >= U)) ans = min(ans,dist[i+ver.size()]);
    }
    printf("%d\n",ans/2+1);

    return 0;
}

Compilation message

golf.cpp: In function 'int build(int, int, int)':
golf.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
      |                         ~~^~~~~~~~~~~~~~~~~
golf.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
      |                     ~~^~~~~~~~~~~~~~~~~
golf.cpp: In function 'int process(vpii&)':
golf.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (i = 0; i < v.size(); i++) c += v[i].first == 0;
      |                 ~~^~~~~~~~~~
golf.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
golf.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:200:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for (i = 0; i < events.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
golf.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for (i = 0; i < events.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
golf.cpp:227:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |     for (i = 0; i < hor.size(); i++) events2.pb(mp(hor[i].l,-(i+ver.size()+1))),events2.pb(mp(hor[i].r,i+ver.size()+1));
      |                 ~~^~~~~~~~~~~~
golf.cpp:228:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |     for (i = 0; i < ver.size(); i++) events2.pb(mp(ver[i].z,-(i+1)));
      |                 ~~^~~~~~~~~~~~
golf.cpp:230:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |     for (i = 0; i < events2.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
golf.cpp:252:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |     for (i = 0; i < ver.size(); i++) {
      |                 ~~^~~~~~~~~~~~
golf.cpp:255:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |     for (i = 0; i < hor.size(); i++) {
      |                 ~~^~~~~~~~~~~~
golf.cpp:262:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |         for (i = 0; i < adjList[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
golf.cpp:268:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  268 |     for (i = 0; i < ver.size(); i++) {
      |                 ~~^~~~~~~~~~~~
golf.cpp:271:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |     for (i = 0; i < hor.size(); i++) {
      |                 ~~^~~~~~~~~~~~
golf.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  188 |     scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:189:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  189 |     for (i = 0; i < N; i++) scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 142276 KB Output is correct
2 Correct 87 ms 142320 KB Output is correct
3 Correct 90 ms 142276 KB Output is correct
4 Correct 89 ms 142420 KB Output is correct
5 Correct 99 ms 143680 KB Output is correct
6 Correct 98 ms 143680 KB Output is correct
7 Correct 97 ms 143684 KB Output is correct
8 Correct 99 ms 143768 KB Output is correct
9 Correct 100 ms 143720 KB Output is correct
10 Correct 99 ms 143756 KB Output is correct
11 Correct 99 ms 143808 KB Output is correct
12 Correct 105 ms 143712 KB Output is correct
13 Correct 98 ms 143684 KB Output is correct
14 Correct 99 ms 143700 KB Output is correct
15 Correct 93 ms 142848 KB Output is correct
16 Correct 95 ms 143384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 142276 KB Output is correct
2 Correct 87 ms 142320 KB Output is correct
3 Correct 90 ms 142276 KB Output is correct
4 Correct 89 ms 142420 KB Output is correct
5 Correct 99 ms 143680 KB Output is correct
6 Correct 98 ms 143680 KB Output is correct
7 Correct 97 ms 143684 KB Output is correct
8 Correct 99 ms 143768 KB Output is correct
9 Correct 100 ms 143720 KB Output is correct
10 Correct 99 ms 143756 KB Output is correct
11 Correct 99 ms 143808 KB Output is correct
12 Correct 105 ms 143712 KB Output is correct
13 Correct 98 ms 143684 KB Output is correct
14 Correct 99 ms 143700 KB Output is correct
15 Correct 93 ms 142848 KB Output is correct
16 Correct 95 ms 143384 KB Output is correct
17 Correct 109 ms 143860 KB Output is correct
18 Correct 100 ms 143784 KB Output is correct
19 Correct 102 ms 143812 KB Output is correct
20 Correct 99 ms 143840 KB Output is correct
21 Correct 99 ms 143804 KB Output is correct
22 Correct 109 ms 143896 KB Output is correct
23 Correct 99 ms 143804 KB Output is correct
24 Correct 101 ms 143808 KB Output is correct
25 Correct 100 ms 143808 KB Output is correct
26 Correct 113 ms 143868 KB Output is correct
27 Correct 93 ms 142900 KB Output is correct
28 Correct 96 ms 143428 KB Output is correct
29 Correct 96 ms 143376 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 142276 KB Output is correct
2 Correct 87 ms 142320 KB Output is correct
3 Correct 90 ms 142276 KB Output is correct
4 Correct 89 ms 142420 KB Output is correct
5 Correct 99 ms 143680 KB Output is correct
6 Correct 98 ms 143680 KB Output is correct
7 Correct 97 ms 143684 KB Output is correct
8 Correct 99 ms 143768 KB Output is correct
9 Correct 100 ms 143720 KB Output is correct
10 Correct 99 ms 143756 KB Output is correct
11 Correct 99 ms 143808 KB Output is correct
12 Correct 105 ms 143712 KB Output is correct
13 Correct 98 ms 143684 KB Output is correct
14 Correct 99 ms 143700 KB Output is correct
15 Correct 93 ms 142848 KB Output is correct
16 Correct 95 ms 143384 KB Output is correct
17 Correct 109 ms 143860 KB Output is correct
18 Correct 100 ms 143784 KB Output is correct
19 Correct 102 ms 143812 KB Output is correct
20 Correct 99 ms 143840 KB Output is correct
21 Correct 99 ms 143804 KB Output is correct
22 Correct 109 ms 143896 KB Output is correct
23 Correct 99 ms 143804 KB Output is correct
24 Correct 101 ms 143808 KB Output is correct
25 Correct 100 ms 143808 KB Output is correct
26 Correct 113 ms 143868 KB Output is correct
27 Correct 93 ms 142900 KB Output is correct
28 Correct 96 ms 143428 KB Output is correct
29 Correct 96 ms 143376 KB Output is correct
30 Correct 2578 ms 335008 KB Output is correct
31 Correct 2483 ms 331716 KB Output is correct
32 Correct 2661 ms 336836 KB Output is correct
33 Correct 2634 ms 337848 KB Output is correct
34 Correct 2540 ms 337204 KB Output is correct
35 Correct 2567 ms 336072 KB Output is correct
36 Correct 2648 ms 340936 KB Output is correct
37 Correct 2650 ms 340136 KB Output is correct
38 Correct 2586 ms 337584 KB Output is correct
39 Correct 2731 ms 340820 KB Output is correct
40 Correct 722 ms 255180 KB Output is correct
41 Correct 745 ms 256684 KB Output is correct
42 Correct 758 ms 259388 KB Output is correct
43 Correct 763 ms 258456 KB Output is correct
44 Correct 779 ms 260844 KB Output is correct
45 Correct 749 ms 257880 KB Output is correct
46 Correct 796 ms 260172 KB Output is correct
47 Correct 751 ms 258244 KB Output is correct
48 Correct 768 ms 260312 KB Output is correct
49 Correct 794 ms 260896 KB Output is correct
50 Correct 104 ms 143428 KB Output is correct
51 Correct 96 ms 143396 KB Output is correct
52 Correct 98 ms 143464 KB Output is correct