//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int N = 1e6+1,inf = 2e9,B = 23,MOD = 30013,LIM = 1e9;
struct TRAP {
int a,b,c,d;
};
vi v;
int idx(int x){
return upper_bound(all(v),x)-v.begin();
}
struct MFT {
int n;
vi bit;
MFT(int nn) {
n = nn;
bit.assign(n+1,0);
}
void put(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = max(bit[i],v);
}
int get(int p) {
int ans = 0;
for (int i=p;i>0;i-=i&-i) ans = max(ans,bit[i]);
return ans;
}
};
int add(int x,int y) {
return ((x+y) >= MOD ? x+y-MOD : x+y);
}
struct SFT {
int n;
vi bit;
SFT(int nn) {
n = nn;
bit.assign(n+1,0);
}
void put(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = add(bit[i],v);
}
void set(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = v;
}
int get(int p) {
int ans = 0;
for (int i=p;i>0;i-=i&-i) ans = add(ans,bit[i]);
return ans;
}
};
void solve() {
int n;
cin >> n;
vector<TRAP> trap(n+1);
for (int i=1;i<=n;i++) cin >> trap[i].a >> trap[i].b >> trap[i].c >> trap[i].d;
for (int i=1;i<=n;i++) {
v.push_back(trap[i].a);
v.push_back(trap[i].b);
v.push_back(trap[i].c);
v.push_back(trap[i].d);
}
sort(v.begin(),v.end());
v.erase(unique(all(v)),v.end());
for (int i=1;i<=n;i++) {
trap[i].a = idx(trap[i].a);
trap[i].b = idx(trap[i].b);
trap[i].c = idx(trap[i].c);
trap[i].d = idx(trap[i].d);
}
int sz = v.size();
MFT mft(sz);
vi dp(n+1,0);
vi in[sz+1],out[sz+1];
for (int i=1;i<=n;i++) in[trap[i].a].push_back(i);
for (int i=1;i<=n;i++) out[trap[i].b].push_back(i);
for (int i=1;i<=sz;i++) {
for (auto it : in[i]) dp[it] = mft.get(trap[it].c)+1;
for (auto it : out[i]) mft.put(trap[it].d,dp[it]);
}
int mx = *max_element(dp.begin()+1,dp.end());
vi x[n+1];
for (int i=1;i<=n;i++) x[dp[i]].push_back(i);
vi ways(n+1,0);
for (auto it : x[1]) ways[it] = add(ways[it],1);
SFT sft(sz);
for (int i=2;i<=n;i++) {
vector<pii> vv;
for (auto it : x[i-1]) vv.push_back({trap[it].b,it});
for (auto it : x[i]) vv.push_back({trap[it].a,it});
sort(vv.begin(),vv.end());
for (auto it : vv) {
if (dp[it.ss] == i) ways[it.ss] = add(ways[it.ss],sft.get(trap[it.ss].c));
else sft.put(trap[it.ss].d,ways[it.ss]);
}
for (auto it : vv) sft.set(trap[it.ss].d,0);
}
int ans = 0;
for (int i=1;i<=n;i++) if (dp[i] == mx) ans = add(ans,ways[i]);
cout << ans << '\n';
//SERIFEFEDARTAR ORZ
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
/* #else
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout); */
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
604 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
600 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
4 ms |
1116 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
3 ms |
1628 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
4 ms |
1668 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
6 ms |
2400 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
15 ms |
4852 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
22 ms |
7000 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
32 ms |
11016 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
60 ms |
22464 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
74 ms |
25084 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
92 ms |
30984 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
104 ms |
29360 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
109 ms |
30656 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
125 ms |
35848 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
105 ms |
27656 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
120 ms |
37784 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
138 ms |
39872 KB |
Unexpected end of file - int32 expected |
