Submission #729882

#TimeUsernameProblemLanguageResultExecution timeMemory
729882Denkatatrapezoid (balkan11_trapezoid)C++14
97 / 100
117 ms13312 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+3;
const int maxq = 4e5+3;
const int mod = 30013;
int i,j,p,q,n,m,k;
pair <int,int> dp[maxn];
pair <int,int> a[maxn];

struct Trapeze
{
    int a[5];///a b c d
}tr[maxn];
struct Coordinate
{
    int val;
    int type;
    int ind;
};
vector <Coordinate> coordinates;
bool ul[maxq],ur[maxq];
pair <int,int> fen[maxq];
void upd(int p,int d,int br)
{
    while(p<=maxq)
    {
        if(d>fen[p].first)
            fen[p] = {d,br};
        else if(d==fen[p].first)
            fen[p].second+=br,fen[p].second%=mod;
        p = (p|(p+1));
    }
}
pair <int,int> rsq(int p)
{
    pair <int,int> ans={0,0};
    while(p>=0)
    {
        if(ans.first<fen[p].first)
            ans = fen[p];
        else if(ans.first==fen[p].first)
            ans.second+=fen[p].second,ans.second%=mod;
        p = ((p&(p+1))-1);
    }
    return ans;
}
bool fff(Coordinate a,Coordinate b)
{
    return a.val<b.val;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>tr[i].a[1]>>tr[i].a[2]>>tr[i].a[3]>>tr[i].a[4];
        coordinates.push_back({tr[i].a[1],1,i});
        coordinates.push_back({tr[i].a[2],2,i});
        coordinates.push_back({tr[i].a[3],3,i});
        coordinates.push_back({tr[i].a[4],4,i});
    }
    sort(coordinates.begin(),coordinates.end(),fff);
    for(i=0;i<coordinates.size();i++)
    {
        auto t = coordinates[i];
        tr[t.ind].a[t.type] = i+1;
    }
    coordinates.push_back({4*n+2,1,n+1});
    tr[n+1].a[3]=4*n+2;
    upd(0,0,1);
    for(i=1;i<=4*n+1;i++)
    {
        auto t = coordinates[i];
        if(t.type==1)
        {
            dp[t.ind] = rsq(tr[t.ind].a[3]);
            dp[t.ind].first++;

        }
        else if(t.type==2)
        {
            upd(tr[t.ind].a[4],dp[t.ind].first,dp[t.ind].second);
        }
    }
    pair <int,int> ans = rsq(4*n+2);
    cout<<ans.first<<" "<<ans.second<<endl;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Coordinate>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(i=0;i<coordinates.size();i++)
      |             ~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...