#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=4e5+10;
const int mod = 30013;
int n,m,a[M],b[M],c[M],d[M];
vector<int> rrh;
struct node
{
int l,r,idx;
};
vector<node> L[N],R[N];
struct segment_tree
{
ii t[4 * N];
ii merged(const ii & l,const ii & r)
{
ii ret ={0,0} ;
ret.first = max(l.first,r.first);
if(l.first == ret.first) ret.second = l.second;
if(r.first == ret.first) ret.second += r.second;
ret.second %= mod;
return ret;
}
void upd(int s, int l, int r, int pos, int val, int cnt)
{
if(l > pos || pos > r) return ;
//cout << l << " " << r << " " << pos << " " << val << "\n";
if(l == r) {
if(t[s].first == val) t[s].second += cnt;
else {
if(val > t[s].first) t[s] = {val,cnt};
}
t[s].second %= mod;
return ;
}
int mid = (l + r)/2;
upd(s *2, l, mid, pos, val, cnt);
upd(s * 2 + 1, mid + 1, r, pos, val, cnt);
t[s] = merged(t[s * 2],t[s * 2 + 1]);
}
ii get(int s, int l, int r, int u, int v)
{
if(l > v || r < u) return {0,0};
//cout << l << " " << r << " " << u << " " << v << " " << t[s].first << "\n";
if(u <= l && r <= v) return t[s];
int mid = (l + r)/2;
return merged(get(s * 2, l, mid, u, v),get(s * 2 + 1, mid + 1, r, u, v));
}
} T[2];
ii merged(const ii & l,const ii & r)
{
ii ret ={0,0} ;
ret.first = max(l.first,r.first);
if(l.first == ret.first) ret.second = l.second;
if(r.first == ret.first) ret.second += r.second;
return ret;
}
int f[M],g[M];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r"))
{
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n;
for(int i = 1;i <= n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
rrh.pb(a[i]),rrh.pb(b[i]),rrh.pb(c[i]),rrh.pb(d[i]);
}
sort(rrh.begin(),rrh.end());
rrh.resize(unique(rrh.begin(),rrh.end()) - rrh.begin());
m = rrh.size();
for(int i = 1;i <= n ; i++) {
a[i] = lower_bound(rrh.begin(),rrh.end(),a[i]) - rrh.begin() + 1;
b[i] = lower_bound(rrh.begin(),rrh.end(),b[i]) - rrh.begin() + 1;
c[i] = lower_bound(rrh.begin(),rrh.end(),c[i]) - rrh.begin() + 1;
d[i] = lower_bound(rrh.begin(),rrh.end(),d[i]) - rrh.begin() + 1;
L[a[i]].pb({c[i],d[i],i});
R[b[i]].pb({c[i],d[i],i});
}
for(int i = 1;i <= m; i++) {
for(node pos : L[i]) {
ii x = T[0].get(1, 1, m, 1, pos.l - 1);
if(x.first == 0) x.second = 1;
x.first++;
x.second %= mod;
f[pos.idx] = x.first;
g[pos.idx] = x.second;
//cerr << T[0].t[1].first << " ";
//cout << i << " " << pos.l << " " << pos.r << " ";
//cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "sa\n";
}
for(node pos : R[i]) {
T[0].upd(1, 1, m, pos.r, f[pos.idx], g[pos.idx]);
// cout << i << " " << pos.l << " " << pos.r << " ";
// cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "\n";
}
}
cout << T[0].t[1].first << " " << T[0].t[1].second % mod;
}
Compilation message
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
trapezoid.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19792 KB |
Output is correct |
| 2 |
Correct |
8 ms |
19968 KB |
Output is correct |
| 3 |
Correct |
13 ms |
20048 KB |
Output is correct |
| 4 |
Correct |
14 ms |
20156 KB |
Output is correct |
| 5 |
Correct |
14 ms |
20048 KB |
Output is correct |
| 6 |
Correct |
17 ms |
20304 KB |
Output is correct |
| 7 |
Correct |
17 ms |
20304 KB |
Output is correct |
| 8 |
Correct |
19 ms |
20560 KB |
Output is correct |
| 9 |
Correct |
26 ms |
21460 KB |
Output is correct |
| 10 |
Correct |
32 ms |
22860 KB |
Output is correct |
| 11 |
Correct |
41 ms |
24520 KB |
Output is correct |
| 12 |
Correct |
83 ms |
27592 KB |
Output is correct |
| 13 |
Correct |
113 ms |
30788 KB |
Output is correct |
| 14 |
Correct |
129 ms |
33552 KB |
Output is correct |
| 15 |
Correct |
127 ms |
30912 KB |
Output is correct |
| 16 |
Correct |
153 ms |
33516 KB |
Output is correct |
| 17 |
Correct |
158 ms |
36008 KB |
Output is correct |
| 18 |
Correct |
132 ms |
34744 KB |
Output is correct |
| 19 |
Correct |
152 ms |
37768 KB |
Output is correct |
| 20 |
Correct |
170 ms |
36288 KB |
Output is correct |
