#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = 30013;
int a[100005], b[100005], c[100005], d[100005];
map <int, int> u;
pair <int, int> niz[200005];
int dp[100005];
int brn[100005];
struct drvo{
int val;
int br;
} seg[1000000];
void upd(int node, int l, int r, int x, int val){
if(l > x || r < x) return;
if(l == r){
seg[node].val = dp[val];
seg[node].br = brn[val];
return;
}
int mid = (l+r)/2;
upd(node*2, l, mid, x, val);
upd(node*2+1, mid+1, r, x, val);
seg[node].val = max(seg[node*2].val, seg[node*2+1].val);
seg[node].br = 0;
if(seg[node].val == seg[node*2].val){
seg[node].br += seg[node*2].br;
}
if(seg[node].val == seg[node*2+1].val){
seg[node].br += seg[node*2+1].br;
}
seg[node].br %= MOD;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
if(l > tr || tl > r) return {0, 1};
if(tl <= l && r <= tr){
return {seg[node].val, seg[node].br};
}
int mid = (l+r)/2;
pair <int, int> a1 = query(node*2, l, mid, tl, tr);
pair <int, int> b1 = query(node*2+1, mid+1, r, tl, tr);
int mn = max(a1.first, b1.first);
int s = 0;
if(a1.first == mn) s += a1.second;
if(b1.first == mn) s += b1.second;
s %= MOD;
return {mn, s};
}
int main(){
ios_base::sync_with_stdio(false);
cout.precision(10);
cout << fixed;
int n;
cin >> n;
vector <int> vec;
for(int i=1; i<=n; i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
vec.push_back(a[i]);
vec.push_back(b[i]);
vec.push_back(c[i]);
vec.push_back(d[i]);
}
sort(vec.begin(), vec.end());
int cnt = 0;
for(auto c : vec){
if(!u[c]) u[c] = ++cnt;
}
for(int i=1; i<=n; i++){
a[i] = u[a[i]];
b[i] = u[b[i]];
c[i] = u[c[i]];
d[i] = u[d[i]];
niz[i] = {c[i] , i};
niz[i+n] = {d[i], i+n};
}
sort(niz+1, niz+1+2*n);
for(int i=1; i<=2*n; i++){
if(niz[i].second > n){
//cout << b << " " << niz[i].second - n << endl;
upd(1, 1, cnt+5, b[niz[i].second - n], niz[i].second - n);
}
else{
int k = niz[i].second;
//cout << a[k] << " " << k << endl;
pair <int, int> rs = query(1, 1, cnt+5, 1, a[k]);
dp[k] = rs.first + 1;
brn[k] = rs.second;
if(dp[k] == 1) brn[k] = 1;
}
}
int res = 0;
int mx = 1;
for(int i=1; i<=n; i++){
mx = max(mx, dp[i]);
}
for(int i=1; i<=n; i++){
//cout << dp[i] << " ";
if(dp[i] == mx){
res += brn[i];
if(res > MOD) res -= MOD;
}
}
cout << mx;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
2 ms |
376 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
3 ms |
504 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
4 ms |
504 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
7 ms |
888 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
10 ms |
1272 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
10 ms |
1144 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
17 ms |
1528 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
36 ms |
3576 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
57 ms |
4340 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
105 ms |
7944 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
241 ms |
15984 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
293 ms |
16880 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
359 ms |
22964 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
381 ms |
19688 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
426 ms |
20472 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
458 ms |
26984 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
322 ms |
17768 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
469 ms |
26600 KB |
Unexpected end of file - int32 expected |
| 20 |
Execution timed out |
524 ms |
28772 KB |
Time limit exceeded |
