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...