#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define x first
#define y second
#define ll long long
#define mod 30030
#define MAX 1000
using namespace std;
struct djoka
{
int x,y,type;
};
int n;
djoka niz[maxn];
int maxx[maxn];
ll num[maxn];
int maks[4*maxn];
ll br[4*maxn];
void update(int v,int l,int r,int lt,int rt,int bigg,int broj)
{
if(l>r || l>rt || lt>r || lt>rt)return;
if(lt<=l && r<=rt)
{
if(maks[v] == bigg)
{
br[v] += broj;
br[v] %= mod;
}
else if(maks[v] < bigg)
{
br[v] = broj;
maks[v] = bigg;
}
return;
}
int mid = (l+r)/2;
update(2*v,l,mid,lt,rt,bigg,broj);
update(2*v+1,mid+1,r,lt,rt,bigg,broj);
}
int najv(int v,int l,int r,int ind)
{
if(l>r || l>ind || r<ind)return 0;
if(l==r)return maks[v];
int mid = (l+r)/2;
if(ind<=mid)return max(maks[v],najv(2*v,l,mid,ind));
return max(maks[v],najv(2*v+1,mid+1,r,ind));
}
ll broj(int v,int l,int r,int ind,int maksimus)
{
if(l>r || l>ind || ind>r)return 0;
if(l==r)
{
if(maks[v] == maksimus)return br[v];
return 0;
}
int mid = (l+r)/2;
ll uk = 0;
if(maks[v] == maksimus)uk += br[v];
if(ind<=mid)return (uk + broj(2*v,l,mid,ind,maksimus))%mod;
return (uk + broj(2*v+1,mid+1,r,ind,maksimus))%mod;
}
bool cmp_x(djoka levi,djoka desni)
{
if(levi.x!=desni.x)return levi.x < desni.x;
return levi.type < desni.type;
}
bool cmp_y(djoka levi,djoka desni)
{
if(levi.y!=desni.y)return levi.y < desni.y;
return levi.type < desni.type;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>niz[2*i].x>>niz[2*i+1].x>>niz[2*i].y>>niz[2*i+1].y;
niz[2*i].type = i+1;
niz[2*i+1].type = -(i+1);
}
sort(niz,niz + 2*n,cmp_y);
for(int i=0;i<2*n;i++)
{
niz[i].y = i;
}
sort(niz,niz + 2*n,cmp_x);
for(int i=0;i<2*n;i++)
{
niz[i].x = i;
}
update(1,0,MAX,0,MAX,0,1);
for(int i=0;i<2*n;i++)
{
int ind = abs(niz[i].type) - 1;
if(niz[i].type > 0)
{
maxx[ind] = najv(1,0,MAX,niz[i].y) + 1;
num[ind] = broj(1,0,MAX,niz[i].y,maxx[ind] - 1);
}
else
{
update(1,0,MAX,niz[i].y+1,MAX,maxx[ind],num[ind]);
}
}
int sol_max = 0;
ll sol_br = 0;
for(int i=0;i<n;i++)
{
//cout<<maxx[i]<<" "<<num[i]<<endl;
if(sol_max == maxx[i])
{
sol_br += num[i];
sol_br %= mod;
}
else if(sol_max < maxx[i])
{
sol_br = num[i];
sol_max = maxx[i];
}
}
cout<<sol_max<<" "<<sol_br<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Partially correct |
2 ms |
376 KB |
Partially correct |
| 4 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
632 KB |
Output isn't correct |
| 9 |
Incorrect |
11 ms |
1016 KB |
Output isn't correct |
| 10 |
Incorrect |
19 ms |
1656 KB |
Output isn't correct |
| 11 |
Incorrect |
25 ms |
1916 KB |
Output isn't correct |
| 12 |
Incorrect |
51 ms |
3448 KB |
Output isn't correct |
| 13 |
Runtime error |
26 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
27 ms |
4508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
26 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
27 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
27 ms |
4436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
27 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
27 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
28 ms |
4416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
