Submission #167268

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167268	2019-12-07T06:58:50 Z	egekabas	Zoltan (COCI16_zoltan)	C++14	Compilation error	0 ms	0 KB

zoltan

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pll;
typedef pair<ld, ld>  pld;
ll n;
ll a[200009];
vector<pll> v;
pll found[200009];
pll seg[800009];
void upd(ll v, ll tl, ll tr, ll id, pll val){
    if(id < tl || id > tr)
        return;
    if(tl == id && tr == id){
        seg[v] = val;
    }
    else{
        ll tm = (tl+tr)/2;
        upd(2*v, tl, tm, id, val);
        upd(2*v+1, tm+1, tr, id, val);
        if(seg[2*v].ff == seg[2*v+1].ff)
            seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
        else if(seg[2*v].ff > seg[2*v+1].ff)
            seg[v] = seg[2*v];
        else
            seg[v] = seg[2*v+1];
    }
}
pll get(ll v, ll tl, ll tr, ll l, ll r){
    if(l < 0)
        return {0, 0};
    if(tl > r || tr < l)
        return {0, 0};
    if(l <= tl && tr <= r){
        return seg[v];
    }
    else{
        ll tm = (tl+tr)/2;
        pll t1 = get(2*v, tl, tm, l, r);
        pll t2 = get(2*v+1, tm+1, tr, l, r);
        if(t1.ff == t2.ff)
            return {t1.ff, (t1.ss + t2.ss)%mod};
        else if(t1.ff > t2.ff)
            return t1;
        else
            return t2;
    }
}
pll dc[200009];
pll ac[200009];
pll tot[200009];
ll mod = 1e9+7;
ll pw(ll x, ll y){
    ll ret = 1;
    while(y > 0){
        if(y%2)
            ret = ret*x%mod;
        y /= 2;
        x = x*x%mod;
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(ll i = 0; i < n; ++i)
        cin >> a[i];
    for(ll i = 0; i < n; ++i)
        v.pb({a[i], i});
    sort(v.begin(), v.end());
    ll i = 0, j = 0;
    while(i < n){
        for(j = i; j < n; ++j){
            if(v[i].ff != v[j].ff)
                break;
            found[j] = get(1, 0, n-1, v[j].ss+1, n-1);
            found[j].ff++;
            if(found[j].ss == 0 && found[j].ff == 1)
                ++found[j].ss;
        }
        for(ll k = i; k < j; ++k)
            upd(1, 0, n-1, v[k].ss, found[k]);
        i = j;
    }
    for(ll i = 0; i < n; ++i){
        dc[i].ff = get(1, 0, n-1, i, i).ff;
        dc[i].ss = get(1, 0, n-1, i, i).ss%mod;
        
    }
    for(ll i = 0; i <= 4*n; ++i)
        seg[i] = {0, 0};
    reverse(v.begin(), v.end());
    i = 0, j = 0;
    while(i < n){
        for(j = i; j < n; ++j){
            if(v[i].ff != v[j].ff)
                break;
            found[j] = get(1, 0, n-1, v[j].ss+1, n-1);
            found[j].ff++;
            if(found[j].ss == 0 && found[j].ff == 1)
                ++found[j].ss;
        }
        for(ll k = i; k < j; ++k)
            upd(1, 0, n-1, v[k].ss, found[k]);
        i = j;
    }
    for(ll i = 0; i < n; ++i){
        ac[i].ff = get(1, 0, n-1, i, i).ff;
        ac[i].ss = get(1, 0, n-1, i, i).ss%mod;
        
    }
    for(ll i = 0; i < n; ++i)
        tot[i] = {ac[i].ff + dc[i].ff-1, ac[i].ss*dc[i].ss%mod};
    ll len = 0;
    ll ans = 0;
    for(ll i = 0; i < n; ++i)
        len = max(len, tot[i].ff);
    for(ll i = 0; i < n; ++i)
        if(tot[i].ff == len){
            ans += pw(2, n-len)*tot[i].ss%mod;
            ans %= mod;
        }
    cout << len << " " << ans << "\n";
}

Compilation message

zoltan.cpp: In function 'void upd(ll, ll, ll, ll, pll)':
zoltan.cpp:29:66: error: 'mod' was not declared in this scope
             seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
                                                                  ^~~
zoltan.cpp:29:66: note: suggested alternative: 'modf'
             seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
                                                                  ^~~
                                                                  modf
zoltan.cpp:29:69: error: no match for 'operator=' (operand types are 'pll {aka std::pair<long long int, long long int>}' and '<brace-enclosed initializer list>')
             seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
                                                                     ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from zoltan.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:367:7: note: candidate: std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_Tp>, 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<_Tp>, 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>&]
       operator=(typename conditional<
       ^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:367:7: 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>&}'
/usr/include/c++/7/bits/stl_pair.h:384: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>&&]
       operator=(typename conditional<
       ^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:384:7: 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>&&}'
/usr/include/c++/7/bits/stl_pair.h:400: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]
  operator=(const pair<_U1, _U2>& __p)
  ^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:400:2: note:   template argument deduction/substitution failed:
zoltan.cpp:29:69: note:   couldn't deduce template parameter '_U1'
             seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
                                                                     ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from zoltan.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:411: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]
  operator=(pair<_U1, _U2>&& __p)
  ^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:411:2: note:   template argument deduction/substitution failed:
zoltan.cpp:29:69: note:   couldn't deduce template parameter '_U1'
             seg[v] = {seg[2*v].ff, (seg[2*v].ss + seg[2*v+1].ss)%mod};
                                                                     ^
zoltan.cpp: In function 'pll get(ll, ll, ll, ll, ll)':
zoltan.cpp:49:44: error: 'mod' was not declared in this scope
             return {t1.ff, (t1.ss + t2.ss)%mod};
                                            ^~~
zoltan.cpp:49:44: note: suggested alternative: 'modf'
             return {t1.ff, (t1.ss + t2.ss)%mod};
                                            ^~~
                                            modf
zoltan.cpp:49:47: error: could not convert '{t1.std::pair<long long int, long long int>::first, <expression error>}' from '<brace-enclosed initializer list>' to 'pll {aka std::pair<long long int, long long int>}'
             return {t1.ff, (t1.ss + t2.ss)%mod};
                                               ^