Submission #624633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624633	2022-08-08T14:51:58 Z	Vladth11	Roads (CEOI20_roads)	C++14	Compilation error	0 ms	0 KB

roads

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <long double, long double> pii;
 
const ll NMAX =200001;
const ll VMAX = 101;
const ll INF = 1e9;
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;
 
set <pii> exista;
 
struct event {
    pii x;
    int stare;
    bool operator < (const event a) {
        if(a.x.first != x.first) {
            return x.first < a.x.first;
        }
        if(a.stare != stare) {
            return stare > a.stare;
        }
        return x.second < a.x.second; /// Nu ar trb sa aiba importanta, dar e necesar sa nu busesc sortarea
    }
};
 
long double swipex;
 
struct segment {
    long double a, b, c, d;
    long double idx;
    long double gety() {
        if(c != a)
            return (long double)b + (long double)(swipex - a) * (long double)(d - b) / (long double)(c - a);
        else
            return (long double)b;
    }
} sgt[NMAX];
 
vector <event> events;
map <pii, pii> mp;
set <pii> already;
 
bool signs(long double a, long double b) {
    if(a < b)
        swap(a, b);
    if(a > 0 && b < 0)
        return 0;
    return 1;
}
 
long double cnt = 0;
 
void adauga(int a, int b) {
    if(a < b)
        swap(a, b);
    cnt++;
    if(already.find({a, b}) != already.end()) return;
    already.insert({a, b});
    segment first = sgt[a];
    segment second = sgt[b];
    if(first.b < second.b) {
        swap(first, second);
    } else if(first.b == second.b) {
        if(first.a < second.a) {
            swap(first, second);
        }
    }
    if(first.a >= second.c) {
        cout << (int)first.a << " " << (int)first.b << " " << (int)second.c << " " << (int)second.d << "\n";
        return;
    }
    if(second.a >= first.c) {
        cout <<(int)first.c << " " << (int)first.d << " " << (int)second.a << " " << (int)second.b << "\n";
        return;
    }
    cout << (int)first.a << " " << (int)first.b << " " << (int)second.a << " " << (int)second.b << "\n";
}
 
struct ura {
    long double first;
    int second;
    bool operator < (const ura a)const {
        if(a.second == -1 && second == -1) {
            return first < a.first;
        }
        if(a.second == -1) {
            return sgt[second].gety() < a.first;
        }
        if(second == -1) {
            return first < sgt[a.second].gety();
        }
        return sgt[second].gety() < sgt[a.second].gety();
    }
};
 
int main() {
    //ifstream cin(".out");
    //ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++) {
        long double a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a > c) {
            swap(b, d);
            swap(a, c);
        } else if(a == c) {
            if(b > d)
                swap(b, d); /// nu stiu daca e nevoie
        }
        sgt[i] = {a, b, c, d, i};
        exista.insert({a, b});
        exista.insert({c, d});
        events.push_back({{a, b}, i});
        events.push_back({{c, d}, -i});
    }
    n += 2;
    sgt[n - 1] = {-INF, -INF, INF, -INF, n - 1};
    events.push_back({{-INF, -INF}, n - 1});
    events.push_back({{INF, -INF}, -(n - 1)});
    sgt[n] = {-INF, INF, INF, INF, n};
    events.push_back({{-INF, INF}, n});
    events.push_back({{INF, INF}, -n});
    sort(events.begin(), events.end());
    set <ura> active;
    for(long double i = 0; i < events.size(); i++) {
        swipex = events[i].x.first;
        if(events[i].stare > 0) {
            active.insert({events[i].x.second, events[i].stare});
        } else {
            if(-events[i].stare < n - 1) {
                auto sus = active.lower_bound({sgt[-events[i].stare].gety(), -1});
                sus = prev(sus);
                auto jos = active.lower_bound({sgt[-events[i].stare].gety(), -1});
                jos = next(jos);
                long double indS = (*sus).second;
                long double indJ = (*jos).second;
                if(mp.find({indS, indJ}) != mp.end())
                    mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {events[i].x.first, -events[i].stare});
                else
                    mp[ {indS, indJ}] = {events[i].x.first, -events[i].stare};
            }
            active.erase({events[i].x.second, -events[i].stare});
            continue;
        }
        if(events[i].stare > n - 2) continue;
        pair <pii, int> x = {events[i].x, events[i].stare};
        auto sus = active.lower_bound({x.first.second, -1});
        sus = prev(sus);
        auto jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
        jos = next(jos);
        int indS = (*sus).second;
        int indJ = (*jos).second;
        if(mp.find({indS, indJ}) == mp.end()) {
            if(sgt[indS].a > sgt[indJ].a) {
                adauga(indS, x.second);
            } else if(sgt[indJ].a != -INF) {
                adauga(indJ, x.second);
            }
        } else {
            pii conectare = mp[ {indS, indJ}];
            adauga(conectare.second, x.second);
        }
        mp[{indS, x.second}] = {x.first, x.second};
        mp[{x.second, indJ}] = {x.first, x.second};
        if(mp.find({indS, indJ}) != mp.end())
            mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {x.first.first, x.second});
        else
            mp[ {indS, indJ}] = {x.first.first, x.second};
    }
    assert(cnt == n - 3);
    return 0;
 
}

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:122:31: warning: narrowing conversion of 'i' from 'int' to 'long double' [-Wnarrowing]
  122 |         sgt[i] = {a, b, c, d, i};
      |                               ^
roads.cpp:129:44: warning: narrowing conversion of '(n - 1)' from 'int' to 'long double' [-Wnarrowing]
  129 |     sgt[n - 1] = {-INF, -INF, INF, -INF, n - 1};
      |                                          ~~^~~
roads.cpp:132:36: warning: narrowing conversion of 'n' from 'int' to 'long double' [-Wnarrowing]
  132 |     sgt[n] = {-INF, INF, INF, INF, n};
      |                                    ^
roads.cpp:175:50: error: no match for 'operator=' (operand types are 'std::map<std::pair<long double, long double>, std::pair<long double, long double> >::mapped_type' {aka 'std::pair<long double, long double>'} and '<brace-enclosed initializer list>')
  175 |         mp[{indS, x.second}] = {x.first, x.second};
      |                                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long double; _T2 = long double; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long double, long double>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long double, long double>&, const std::__nonesuch&>::type' {aka 'const std::pair<long double, long double>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long double; _T2 = long double; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long double, long double>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long double, long double>&&, std::__nonesuch&&>::type' {aka 'std::pair<long double, long double>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long double; _T2 = long double]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
roads.cpp:175:50: note:   couldn't deduce template parameter '_U1'
  175 |         mp[{indS, x.second}] = {x.first, x.second};
      |                                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long double; _T2 = long double]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
roads.cpp:175:50: note:   couldn't deduce template parameter '_U1'
  175 |         mp[{indS, x.second}] = {x.first, x.second};
      |                                                  ^
roads.cpp:176:50: error: no match for 'operator=' (operand types are 'std::map<std::pair<long double, long double>, std::pair<long double, long double> >::mapped_type' {aka 'std::pair<long double, long double>'} and '<brace-enclosed initializer list>')
  176 |         mp[{x.second, indJ}] = {x.first, x.second};
      |                                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long double; _T2 = long double; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long double, long double>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long double, long double>&, const std::__nonesuch&>::type' {aka 'const std::pair<long double, long double>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long double; _T2 = long double; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long double, long double>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long double, long double>&&, std::__nonesuch&&>::type' {aka 'std::pair<long double, long double>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long double; _T2 = long double]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
roads.cpp:176:50: note:   couldn't deduce template parameter '_U1'
  176 |         mp[{x.second, indJ}] = {x.first, x.second};
      |                                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long double; _T2 = long double]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
roads.cpp:176:50: note:   couldn't deduce template parameter '_U1'
  176 |         mp[{x.second, indJ}] = {x.first, x.second};
      |                                                  ^