# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
729882 | Denkata | trapezoid (balkan11_trapezoid) | C++14 | 117 ms | 13312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |