Submission #307324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307324	2020-09-27T19:37:00 Z	aZvezda	Ideal city (IOI12_city)	C++14	Compilation error	0 ms	0 KB

city

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 1e5 + 10;
vector<ll> g[MAX_N];
vector<pair<ll, pair<ll, ll> > > inter;
vector<pair<ll, ll> > grid;
ll n, ret = 0;

ll dfs(ll x, ll p) {
    ll sz = inter[x].second.second - inter[x].second.first + 1;
    for(auto it : g[x]) {
        if(it == p) {continue;}
        sz += dfs(it, x);
    }
    ret += sz * (n - sz);
    return sz;
}

void generateTree() {
    inter.resize(0);
    sort(grid.begin(), grid.end());
    for(ll i = 0; i < n; i ++) {
        ll j = i;
        while(j + 1 < n && grid[j + 1].first == grid[i].first && grid[j + 1].second == grid[j].second + 1) {j ++;}
        inter.push_back({grid[i].first, {grid[i].second, grid[j].second}});
        i = j;
    }
    for(ll i = 0; i < inter.size(); i ++) {
        g[i].resize(0);
    }
    ll r = 0;
    for(ll l = 0; l < inter.size(); l ++) {
        while(r < inter.size() && inter[r].first == inter[l].first) {r ++;}
        if(r == inter.size()) {
            break;
        }
        while(r < n - 1 && inter[r].second.second < inter[l].second.first && inter[r + 1].first == inter[l].first + 1) {r ++;}
        while(r < n - 1 && inter[r].second.second <= inter[l].second.second && inter[r + 1].first == inter[l].first + 1) {
            g[l].push_back(r);
            g[r].push_back(l);
            r ++;
        }
        if(r != n && inter[r].second.first <= inter[l].second.second && inter[r].first == inter[l].first + 1) {
            g[l].push_back(r);
            g[r].push_back(l);
        }
    }
    dfs(0, -1);
}


int DistanceSum(int N, int *X, int *Y) {
    n = N;;
    for(int i = 0; i < n; i ++) {
        grid[i] = {&X[i], &Y[i]};
    }
    return ret;
}

/*

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(ll i = 0; i < n; i ++) {
        ll x, y;
        cin >> x >> y;
        grid.push_back({x, y});
    }
    generateTree();
    for(ll i = 0; i < n; i ++) {
        swap(grid[i].first, grid[i].second);
    }
    generateTree();
    cout << ret << endl;
    return 0;
}*/

/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

Compilation message

city.cpp: In function 'void generateTree()':
city.cpp:40:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(ll i = 0; i < inter.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~
city.cpp:44:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(ll l = 0; l < inter.size(); l ++) {
      |                   ~~^~~~~~~~~~~~~~
city.cpp:45:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(r < inter.size() && inter[r].first == inter[l].first) {r ++;}
      |               ~~^~~~~~~~~~~~~~
city.cpp:46:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(r == inter.size()) {
      |            ~~^~~~~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:67:32: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} and '<brace-enclosed initializer list>')
   67 |         grid[i] = {&X[i], &Y[i]};
      |                                ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from city.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:378: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_no_braces&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch_no_braces&>::type = const std::pair<long long int, long long int>&]'
  378 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:381:51: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch_no_braces&>::type' {aka 'const std::pair<long long int, long long int>&'}
  378 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~              
  379 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                  
  380 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
  381 |   const pair&, const __nonesuch_no_braces&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_pair.h:389: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_no_braces&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch_no_braces&&>::type = std::pair<long long int, long long int>&&]'
  389 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:392:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch_no_braces&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  389 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  390 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  391 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  392 |   pair&&, __nonesuch_no_braces&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_pair.h:405: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 long int; _T2 = long long int]'
  405 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:405:2: note:   template argument deduction/substitution failed:
city.cpp:67:32: note:   couldn't deduce template parameter '_U1'
   67 |         grid[i] = {&X[i], &Y[i]};
      |                                ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from city.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:416: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 long int; _T2 = long long int]'
  416 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:416:2: note:   template argument deduction/substitution failed:
city.cpp:67:32: note:   couldn't deduce template parameter '_U1'
   67 |         grid[i] = {&X[i], &Y[i]};
      |                                ^