oj.uz

Submission #345998

# Submission time Handle Problem Language Result Execution time Memory
345998 2021-01-08T20:53:39 Z doowey Roads (CEOI20_roads) C++14
0 / 100
 109 ms 7004 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
const ld inf = 1e9;
ld C;

struct segm{
    pdd A;
    pdd B;
    int id;
    bool operator< (const segm &t) const {
        ld fa;
        if(A.fi == B.fi){
            fa = A.se;
        }
        else{
            fa = (B.se-A.se)/(B.fi-A.fi) * (C - A.fi) + A.se;
        }
        ld fb;
        if(t.A.fi == t.B.fi){
            fb = t.A.se;
        }
        else{
            fb = (t.B.se-t.A.se)/(t.B.fi-t.A.fi) * (C-t.A.fi) + t.A.se;
        }
        return fa < fb;
    }
    bool operator== (segm &t) const {
        return (id == t.id);
    }
};

pdd ai[N], bi[N];
pdd rig[N];
bool act[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<pair<ld,int>> eve;
    for(int i = 0 ; i < n; i ++) {
        cin >> ai[i].fi >> ai[i].se >> bi[i].fi >> bi[i].se;
        if(ai[i] > bi[i]) swap(ai[i], bi[i]);
        eve.push_back(mp(ai[i].fi,i));
        eve.push_back(mp(bi[i].fi,i));
    }
    set<segm> sq;
    C = -inf;
    sq.insert({mp(-inf,inf),mp(inf,inf),n});
    rig[n]=mp(-inf,-inf);
    sort(eve.begin(), eve.end());
    int nid;
    int cr = 0;
    for(auto ii : eve){
        C = ii.fi;
        if(!act[ii.se]){
            auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
            nid = it->id;

            if(rig[nid] != mp(-inf,-inf)){
                cout << (int)rig[nid].fi << " " << (int)rig[nid].se << " " << (int)ai[ii.se].fi << " " << (int)ai[ii.se].se << "\n";
            }

            rig[ii.se] = ai[ii.se];
            rig[nid] = ai[ii.se];
            act[ii.se]=true;
            sq.insert({ai[ii.se],bi[ii.se],ii.se});
        }
        else{
            sq.erase({ai[ii.se],bi[ii.se],ii.se});
            auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
            nid = it->id;
            rig[nid]=bi[ii.se];
        }
    }
    return 0;
}

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:66:9: warning: unused variable 'cr' [-Wunused-variable]
   66 |     int cr = 0;
      |         ^~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 109 ms 7004 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Failed 3 ms 620 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Failed 3 ms 620 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Failed 3 ms 620 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Failed 3 ms 620 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 109 ms 7004 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Failed 3 ms 620 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
6 Halted 0 ms 0 KB -