Submission #1129657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129657		I_FloPPed21	trapezoid (balkan11_trapezoid)	C++20	Compilation error	0 ms	0 KiB

trapezoid

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int N=2e5+1;
map<int,int>mp;
struct trapezoid
{
    int a,b,c,d;
} v[N];
int n,cnt;
vector<int>buffer;
void change(int i)
{
    v[i].a=mp[v[i].a];
    v[i].b=mp[v[i].b];
    v[i].c=mp[v[i].c];
    v[i].d=mp[v[i].d];
}
void norm()
{
    sort(buffer.begin(),buffer.end());
    for(auto u:buffer)
    {
        if(mp[u]==0)
        {
            cnt++;
            mp[u]=cnt;
        }
    }
    for(int i=1; i<=n; i++)
        change(i);
    buffer.clear();
    mp.clear();
}
int dp[N];//cea mai lunga secventa op care se termina aci;
int aib[4*N];
void update(int poz,int val)
{
    for(int i=poz; i<=4*n; i+=(i&-i))
    {
        aib[i]=max(aib[i],val);
    }
}
int query(int poz)
{
    int maxx=0;
    for(int i=poz; i>0; i-=(i&-i))
        maxx=max(maxx,aib[i]);
    return maxx;
}
void clean_aib()
{
    for(int i=1; i<=4*n; i++)
        aib[i]=0;
}
const int mod=30013;
int dp2[N];
void sum_aib(int poz,int val)
{
    for(int i=poz; i<=4*n; i+=(i&-i))
    {
        aib[i]+=val;
        aib[i]%=mod;
    }
}
vector<int>adj[N];
int query_sum(int poz)
{
    int sum=0;
    for(int i=poz; i>0; i-=(i&-i))
    {
        sum+=aib[i];
        sum%=mod;
    }
    return sum;
}
void calculate(int necesar)
{
    vector<int>a;
    for(auto u:adj[necesar])
        a.push_back(u);
    for(auto u:adj[necesar-1])
        a.push_back(u);
    sort(a.begin(),a.end());
    set<pair<int,int>>st;
    for(auto val:a)
    {
        while(!st.empty()&&(*st.begin()).first<=v[val].c)
        {
            int nod=(*st.begin()).second;
            st.erase(st.begin());
            sum_aib(max(v[nod].b,1),dp2[nod]);
        }

        if(dp[val]==necesar)
        {
            dp2[val]=query_sum(v[val].a);
        }
        else if(dp[val]==necesar-1)
        {
            st.insert({v[val].d,val});
        }
    }

    while(!st.empty())
    {
        int nod=(*st.begin()).second;
        st.erase(st.begin());
        sum_aib(max(v[nod].b,1),dp2[nod]);
    }
    for(auto u:adj[necesar-1])
    {
        sum_aib(max(v[u].b,1ll),-dp2[u]);
        dp2[u]=0;
    }
}

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i].a>>v[i].b>>v[i].c>>v[i].d;
        buffer.push_back(v[i].a);
        buffer.push_back(v[i].b);
        buffer.push_back(v[i].c);
        buffer.push_back(v[i].d);
    }

    norm();
    sort(v+1,v+n+1,[](trapezoid x,trapezoid y)
    {
        return x.c<y.c;
    });
    int ans=0;
    set<pair<int,int>>sd;
    for(int i=1; i<=n; i++)
    {
        while(!sd.empty()&&(*sd.begin()).first<=v[i].c)
        {
            int nod=(*sd.begin()).second;
            update(v[nod].b,dp[nod]);
            sd.erase(sd.begin());
        }
        int val=query(v[i].a);
        dp[i]=val+1;
        sd.insert({v[i].d,i});
        ans=max(ans,dp[i]);
    }
    adj[0].push_back(0);
    dp2[0]=1;
    clean_aib();
    for(int i=1; i<=n; i++)
    {
        adj[dp[i]].push_back(i);
    }
    for(int i=1; i<=ans; i++)
        calculate(i);

    int modes=0;
    for(int i=1; i<=n; i++)
    {
        modes+=dp2[i];
        modes%=mod;
    }
    cout<<ans<<" ";
    cout<<modes<<'\n';
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void calculate(int)':
trapezoid.cpp:116:20: error: no matching function for call to 'max(int&, long long int)'
  116 |         sum_aib(max(v[u].b,1ll),-dp2[u]);
      |                 ~~~^~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from trapezoid.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
trapezoid.cpp:116:20: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  116 |         sum_aib(max(v[u].b,1ll),-dp2[u]);
      |                 ~~~^~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from trapezoid.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
trapezoid.cpp:116:20: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  116 |         sum_aib(max(v[u].b,1ll),-dp2[u]);
      |                 ~~~^~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from trapezoid.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
trapezoid.cpp:116:20: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  116 |         sum_aib(max(v[u].b,1ll),-dp2[u]);
      |                 ~~~^~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from trapezoid.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
trapezoid.cpp:116:20: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  116 |         sum_aib(max(v[u].b,1ll),-dp2[u]);
      |                 ~~~^~~~~~~~~~~~