Submission #758693

#	Time	Username	Problem	Language	Result	Execution time	Memory
758693		bgnbvnbv	trapezoid (balkan11_trapezoid)	C++14	100 / 100	130 ms	24784 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const string taskname = "";
#define FILE 0

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second

#define bit(i, a) (((a)>>(i))&1)
#define ms(a, v) memset(a, v, sizeof(a))
#define lb(a, v) lower_bound(a.begin(), a.end(), v)
#define ub(a, v) upper_bound(a.begin(), a.end(), v)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef vector<bool> vb;




const ll mod = 30013;
const ll maxn = 2e5+13;
const ll inf = 1e9+5;
const ll infl = 1e18+5;
char tochar[] = {'0','1','2','3','4','5','6','7','8','9'};
const bool testcases = true;
const ll maxN=2e5+10;
ll n,a[maxN],b[maxN],c[maxN],d[maxN];
#define pli pair<ll,ll>
vector<ll> cor;
vector<pli>vec,vec1;
ll dp[maxN],cnt[maxN];
struct node
{
    ll val,cnt;
    node ()
    {
        val=-inf,cnt=0;
    }
    node operator+(const node&o)
    {
        node ans;
        ans=o;
        if(ans.val<val)
        {
            ans.val=val;
            ans.cnt=cnt;
        }
        else if(ans.val==val)
        {
            ans.cnt+=cnt;
            ans.cnt%=mod;
        }
        return ans;
    }
}st[4*maxN];
void update(ll pos,ll val1,ll val2,ll id=1,ll l=1,ll r=2*n)
{
    if(l==r)
    {
        node cc;
        cc.val=val1;
        cc.cnt=val2;
        st[id]=st[id]+cc;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val1,val2,id*2,l,mid);
    else update(pos,val1,val2,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=2*n)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ///freopen((taskname+".inp").c_str(), "r", stdin);
    ///freopen((taskname+".out").c_str(), "w", stdout);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vec.pb({b[i],i});
        vec1.pb({a[i],i});
        cor.pb(c[i]);
        cor.pb(d[i]);
    }
    sort(cor.begin(),cor.end());
    for(int i=1;i<=n;i++)
    {
        c[i]=lower_bound(cor.begin(),cor.end(),c[i])-cor.begin()+1;
        d[i]=lower_bound(cor.begin(),cor.end(),d[i])-cor.begin()+1;
    }
    sort(vec1.begin(),vec1.end());
    sort(vec.begin(),vec.end());
    ll j=0;
    for(int i=0;i<vec1.size();i++)
    {
        while(j<vec.size()&&vec[j].fi<=vec1[i].fi)
        {
            update(d[vec[j].se],dp[vec[j].se],cnt[vec[j].se]);
            j++;
        }
        dp[vec1[i].se]=1;
        cnt[vec1[i].se]=1;
        ll x=get(1,c[vec1[i].se]).val;
        ll ct=get(1,c[vec1[i].se]).cnt;
        if(dp[vec1[i].se]<x+1)
        {
            dp[vec1[i].se]=x+1;
            cnt[vec1[i].se]=ct;
        }
        else if(dp[vec1[i].se]==x+1)
        {
            cnt[vec1[i].se]+=ct;
            cnt[vec1[i].se]%=mod;
        }
    }
    ll mx=0,ctt=0;
    for(int i=1;i<=n;i++)
    {
        if(dp[i]>mx)
        {
            mx=dp[i];
            ctt=cnt[i];
        }
        else if(dp[i]==mx) ctt+=cnt[i],ctt%=mod;
    }
    cout << mx <<' '<<ctt;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
trapezoid.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     ll mid=l+r>>1;
      |            ~^~
trapezoid.cpp: In function 'node get(ll, ll, ll, ll, ll)':
trapezoid.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     ll mid=l+r>>1;
      |            ~^~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i=0;i<vec1.size();i++)
      |                 ~^~~~~~~~~~~~
trapezoid.cpp:118:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         while(j<vec.size()&&vec[j].fi<=vec1[i].fi)
      |               ~^~~~~~~~~~~

• Subtask 1: 100 / 100