oj.uz

Submission #493855

# Submission time Handle Problem Language Result Execution time Memory
493855 2021-12-13T08:16:10 Z LittleCube Roads (CEOI20_roads) C++14
0 / 100
 103 ms 4292 KB 
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

int N, vis[200005];
pll p[100005][2];
pii ans[100005];
vector<pii> v;

int curx = -1e8;
struct sort_by_y
{
    double intersect(int a, int x) const
    {
        if (p[a][0].F == p[a][1].F)
            return (p[a][0].S + p[a][1].S) / 2;
        
        return p[a][0].S + double(p[a][1].S - p[a][0].S) * double(x - p[a][0].F) / double(p[a][1].F - p[a][0].F);
    }
    bool operator()(int a, int b) const
    {
        int curx = max(p[a][0].F, p[b][0].F);
        if (p[a][0].F == p[a][1].F)
            curx = p[a][0].F;
        if (p[b][0].F == p[b][1].F)
            curx = p[b][0].F;
        return intersect(a, curx) < intersect(b, curx);
    }
};

map<int, pii, sort_by_y> sweep;

signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> p[i][0].F >> p[i][0].S >> p[i][1].F >> p[i][1].S;
    for (int i = 1; i <= N; i++)
        if (p[i][0] > p[i][1])
            swap(p[i][0], p[i][1]);
    for (int i = 1; i <= N; i++)
    {
        v.emplace_back(pii{i, 0});
        v.emplace_back(pii{i, 1});
    }
    p[0][0] = pii{-1e8, 1e8}, p[0][1] = pii{1e8, 1e8};
    sort(v.begin(), v.end(), [&](pii p1, pii p2)
         {
             if (p[p1.F][p1.S].F == p[p2.F][p2.S].F)
             {
                 if (p1.F == p2.F)
                     return p1.S < p2.S;
                 return p1.S > p2.S;
             }
             else
                 return p[p1.F][p1.S].F < p[p2.F][p2.S].F;
         });
    sweep[0] = {0, 0};
    for (int i = 0; i < v.size(); i++)
    {
        
        if (v[i].S == 1)
        {
            //cout << "remove " << v[i].F << '\n';
            auto iter = sweep.erase(sweep.find(v[i].F));
            sweep[iter->F] = v[i];
        }
        else
        {
            //cout << "insert " << v[i].F << '\n';
            auto iter = sweep.lower_bound(v[i].F);
            ans[v[i].F] = sweep[iter->F];
            //cout << "...with answer " << ans[v[i].F].F << " " << ans[v[i].F].S << '\n';
            sweep[v[i].F] = v[i];
            iter = sweep.upper_bound(v[i].F);
            sweep[iter->F] = v[i];
        }
    }

    for (int i = 1; i <= N; i++)
        if(ans[i] != pii{0, 0})
            cout << p[i][0].F << " " << p[i][0].S << " " << p[ans[i].F][ans[i].S].F << " " << p[ans[i].F][ans[i].S].S << "\n";
}

/*
4 
1 1 3 2
1 3 5 3
6 1 5 5
1 4 4 5
*/

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Failed 100 ms 4292 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Failed 2 ms 332 KB Condition failed: "!Cross(S[*pi], S[*pa])"
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Failed 3 ms 332 KB Condition failed: "!Cross(S[*pi], S[*pa])"
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Failed 3 ms 332 KB Condition failed: "!Cross(S[*pi], S[*pa])"
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Failed 3 ms 332 KB Condition failed: "!Cross(S[*pi], S[*pa])"
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

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