Submission #1308775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308775		Rares	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

///acum n*log (maxval) cu aliens trick+cht trick
#include <bits/stdc++.h>
#include "aliens.h"
/**using namespace std;
ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/


const int MAXN=1e5+10;
typedef long long ll;
ll INF=1e18;

int n,m,k;
ll dp[MAXN];
int cnt[MAXN];
pair <ll,ll> d[MAXN];
vector <pair <int,int>> aux,v;

bool cmp (pair <int,int> a, pair <int,int> b){
    if (a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}

ll f (pair <ll,ll> d, ll x){
    return d.first*x+d.second;
}

bool g (int i, int j, int x){
    ///daca j <= i atunci scot i
    if (f (d[i],x)>f (d[j],x)) return true;
    return cnt[i]<=cnt[j];
}


ll solve (ll x){
    dp[0]=cnt[0]=0;
    for (int i=1;i<=n;++i){
        dp[i]=INF;
        cnt[i]=1e9;
    }
    stack <int> st;
    for (int i=0;i<=n;++i){
        if (i){
            dp[i]=v[i].second*v[i].second;
            if (st.empty ()){
                cnt[i]=1;
            }
            else{
                while (st.size ()>=2){
                    int i1=st.top ();
                    st.pop ();
                    int i2=st.top ();
                    st.push (i1);

                    if (g (i1,i2,v[i].second)){
                        st.pop ();
                    }
                    else
                        break;
                }
                int pcrt=st.top ();
                dp[i]+=f (d[pcrt],v[i].second);
                cnt[i]=cnt[pcrt]+1;
            }
        }

        if (i<=n-1){
            ll acrt=-2*(v[i+1].first-1);
            ll bcrt=dp[i]+1LL*(v[i+1].first-1)*(v[i+1].first-1)+x;
            ll aux=max (0,v[i].second-v[i+1].first+1);
            aux*=aux;
            bcrt-=aux;
            d[i]={acrt,bcrt};
            st.push (i);
        }

    }

    return cnt[n];
}

ll take_photos (int N, int M, int K, vector <int> r, vector <int> c){
    n=N;
    m=M;
    k=K;
    for (int i=0;i<n;++i){
        r[i]++;
        c[i]++;
        if (r[i]>c[i]){
            swap (r[i],c[i]);
        }
        aux.push_back ({r[i],c[i]});
    }

    sort (aux.begin (),aux.end (),cmp);
    v.push_back ({0,0});
    int cmax=0;
    for (auto x:aux){
        if (x.second>cmax){
            cmax=x.second;
            v.push_back (x);
        }
    }

    n=v.size ()-1;

    ll st=0,dr=1e12,rez;
    while (st<=dr){
        ll mij=(st+dr)/2;
        if (solve (mij)>k){
            st=mij+1;
        }
        else{
            dr=mij-1;
            rez=mij;
        }
    }
    solve (rez);


    return dp[n]-k*rez;
}

Compilation message (stderr)

aliens.cpp:18:1: error: 'pair' does not name a type
   18 | pair <ll,ll> d[MAXN];
      | ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from aliens.cpp:2:
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   19 | vector <pair <int,int>> aux,v;
      |         ^~~~
      |         std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:19:1: error: 'vector' does not name a type
   19 | vector <pair <int,int>> aux,v;
      | ^~~~~~
aliens.cpp:21:11: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |           ^~~~
      |           std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:21:17: error: expected primary-expression before 'int'
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                 ^~~
aliens.cpp:21:21: error: expected primary-expression before 'int'
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                     ^~~
aliens.cpp:21:29: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                             ^~~~
      |                             std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:21:35: error: expected primary-expression before 'int'
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                                   ^~~
aliens.cpp:21:39: error: expected primary-expression before 'int'
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                                       ^~~
aliens.cpp:21:45: error: expression list treated as compound expression in initializer [-fpermissive]
   21 | bool cmp (pair <int,int> a, pair <int,int> b){
      |                                             ^
aliens.cpp:26:7: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   26 | ll f (pair <ll,ll> d, ll x){
      |       ^~~~
      |       std::pair
/usr/include/c++/13/bits/stl_pair.h:187:12: note: 'std::pair' declared here
  187 |     struct pair
      |            ^~~~
aliens.cpp:26:15: error: expected primary-expression before ',' token
   26 | ll f (pair <ll,ll> d, ll x){
      |               ^
aliens.cpp:26:18: error: expected primary-expression before '>' token
   26 | ll f (pair <ll,ll> d, ll x){
      |                  ^
aliens.cpp:26:20: error: 'd' was not declared in this scope
   26 | ll f (pair <ll,ll> d, ll x){
      |                    ^
aliens.cpp:26:26: error: expected primary-expression before 'x'
   26 | ll f (pair <ll,ll> d, ll x){
      |                          ^
aliens.cpp:26:27: error: expression list treated as compound expression in initializer [-fpermissive]
   26 | ll f (pair <ll,ll> d, ll x){
      |                           ^
aliens.cpp: In function 'bool g(int, int, int)':
aliens.cpp:32:12: error: 'd' was not declared in this scope
   32 |     if (f (d[i],x)>f (d[j],x)) return true;
      |            ^
aliens.cpp:32:11: error: 'f' cannot be used as a function
   32 |     if (f (d[i],x)>f (d[j],x)) return true;
      |         ~~^~~~~~~~
aliens.cpp:32:22: error: 'f' cannot be used as a function
   32 |     if (f (d[i],x)>f (d[j],x)) return true;
      |                    ~~^~~~~~~~
aliens.cpp: In function 'll solve(ll)':
aliens.cpp:43:5: error: 'stack' was not declared in this scope; did you mean 'std::stack'?
   43 |     stack <int> st;
      |     ^~~~~
      |     std::stack
In file included from /usr/include/c++/13/stack:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:160:
/usr/include/c++/13/bits/stl_stack.h:99:11: note: 'std::stack' declared here
   99 |     class stack
      |           ^~~~~
aliens.cpp:43:12: error: expected primary-expression before 'int'
   43 |     stack <int> st;
      |            ^~~
aliens.cpp:46:19: error: 'v' was not declared in this scope
   46 |             dp[i]=v[i].second*v[i].second;
      |                   ^
aliens.cpp:47:17: error: 'st' was not declared in this scope; did you mean 'std'?
   47 |             if (st.empty ()){
      |                 ^~
      |                 std
aliens.cpp:64:27: error: 'd' was not declared in this scope
   64 |                 dp[i]+=f (d[pcrt],v[i].second);
      |                           ^
aliens.cpp:64:46: error: 'f' cannot be used as a function
   64 |                 dp[i]+=f (d[pcrt],v[i].second);
      |                                              ^
aliens.cpp:70:25: error: 'v' was not declared in this scope
   70 |             ll acrt=-2*(v[i+1].first-1);
      |                         ^
aliens.cpp:72:20: error: 'max' was not declared in this scope
   72 |             ll aux=max (0,v[i].second-v[i+1].first+1);
      |                    ^~~
aliens.cpp:72:20: note: suggested alternatives:
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   'std::max'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
In file included from /usr/include/c++/13/algorithm:63:
/usr/include/c++/13/bits/ranges_algo.h:2928:29: note:   'std::ranges::max'
 2928 |   inline constexpr __max_fn max{};
      |                             ^~~
aliens.cpp:75:13: error: 'd' was not declared in this scope
   75 |             d[i]={acrt,bcrt};
      |             ^
aliens.cpp:76:13: error: 'st' was not declared in this scope; did you mean 'std'?
   76 |             st.push (i);
      |             ^~
      |             std
aliens.cpp: At global scope:
aliens.cpp:84:38: error: 'vector' has not been declared
   84 | ll take_photos (int N, int M, int K, vector <int> r, vector <int> c){
      |                                      ^~~~~~
aliens.cpp:84:45: error: expected ',' or '...' before '<' token
   84 | ll take_photos (int N, int M, int K, vector <int> r, vector <int> c){
      |                                             ^
aliens.cpp: In function 'll take_photos(int, int, int, int)':
aliens.cpp:89:9: error: 'r' was not declared in this scope
   89 |         r[i]++;
      |         ^
aliens.cpp:90:9: error: 'c' was not declared in this scope
   90 |         c[i]++;
      |         ^
aliens.cpp:92:13: error: 'swap' was not declared in this scope
   92 |             swap (r[i],c[i]);
      |             ^~~~
aliens.cpp:92:13: note: suggested alternatives:
In file included from /usr/include/c++/13/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:181:
/usr/include/c++/13/bits/regex.h:2230:5: note:   'std::__cxx11::swap'
 2230 |     swap(match_results<_Bi_iter, _Alloc>& __lhs,
      |     ^~~~
In file included from /usr/include/c++/13/bits/stl_pair.h:61:
/usr/include/c++/13/bits/move.h:189:5: note:   'std::swap'
  189 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/13/bits/move.h:189:5: note:   'std::swap'
In file included from /usr/include/c++/13/compare:37,
                 from /usr/include/c++/13/bits/stl_pair.h:65:
/usr/include/c++/13/concepts:243:43: note:   'std::ranges::__cust::swap'
  243 |       inline constexpr __cust_swap::_Swap swap{};
      |                                           ^~~~
In file included from /usr/include/c++/13/exception:164,
                 from /usr/include/c++/13/stdexcept:38,
                 from /usr/include/c++/13/system_error:43,
                 from /usr/include/c++/13/bits/ios_base.h:46,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54:
/usr/include/c++/13/bits/exception_ptr.h:230:5: note:   'std::__exception_ptr::swap'
  230 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
In file included from /usr/include/c++/13/filesystem:49,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:200:
/usr/include/c++/13/bits/fs_path.h:736:15: note:   'std::filesystem::__cxx11::swap'
  736 |   inline void swap(path& __lhs, path& __rhs) noexcept { __lhs.swap(__rhs); }
      |               ^~~~
/usr/include/c++/13/concepts:183:35: note:   'std::ranges::__cust_swap::swap'
  183 |       template<typename _Tp> void swap(_Tp&, _Tp&) = delete;
      |                                   ^~~~
aliens.cpp:94:9: error: 'aux' was not declared in this scope
   94 |         aux.push_back ({r[i],c[i]});
      |         ^~~
aliens.cpp:97:11: error: 'aux' was not declared in this scope
   97 |     sort (aux.begin (),aux.end (),cmp);
      |           ^~~
aliens.cpp:97:5: error: 'sort' was not declared in this scope
   97 |     sort (aux.begin (),aux.end (),cmp);
      |     ^~~~
aliens.cpp:97:5: note: suggested alternatives:
In file included from /usr/include/c++/13/algorithm:73:
/usr/include/c++/13/pstl/glue_algorithm_defs.h:296:1: note:   'std::sort'
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
/usr/include/c++/13/bits/ranges_algo.h:1801:30: note:   'std::ranges::sort'
 1801 |   inline constexpr __sort_fn sort{};
      |                              ^~~~
aliens.cpp:98:5: error: 'v' was not declared in this scope
   98 |     v.push_back ({0,0});
      |     ^
aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~