#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
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)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 4 |
Correct |
6 ms |
13012 KB |
Output is correct |
| 5 |
Correct |
7 ms |
13140 KB |
Output is correct |
| 6 |
Correct |
9 ms |
13316 KB |
Output is correct |
| 7 |
Correct |
9 ms |
13396 KB |
Output is correct |
| 8 |
Correct |
11 ms |
13640 KB |
Output is correct |
| 9 |
Correct |
16 ms |
14164 KB |
Output is correct |
| 10 |
Correct |
25 ms |
15428 KB |
Output is correct |
| 11 |
Correct |
34 ms |
15936 KB |
Output is correct |
| 12 |
Correct |
69 ms |
18984 KB |
Output is correct |
| 13 |
Correct |
75 ms |
20172 KB |
Output is correct |
| 14 |
Correct |
94 ms |
21504 KB |
Output is correct |
| 15 |
Correct |
98 ms |
22040 KB |
Output is correct |
| 16 |
Correct |
108 ms |
22572 KB |
Output is correct |
| 17 |
Correct |
117 ms |
23280 KB |
Output is correct |
| 18 |
Correct |
98 ms |
23840 KB |
Output is correct |
| 19 |
Correct |
124 ms |
24408 KB |
Output is correct |
| 20 |
Correct |
130 ms |
24784 KB |
Output is correct |
