#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 ;
if(l == r) {
if(t[s].first == val) t[s].second += cnt;
else 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};
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;
//cerr << a[i] << " " << b[i] << " " << c[i] << " " << d[i] << "\n";
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 = merged(T[0].get(1, 1, m, 1, pos.l - 1),T[1].get(1, 1, m, pos.r + 1, m));
if(x.first == 0) x.second = 1;
x.first++;
x.second %= mod;
f[pos.idx] = x.first;
g[pos.idx] = x.second;
// cout << i << " " << pos.l << " " << pos.r << " ";
// cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "\n";
}
for(node pos : R[i]) {
T[0].upd(1, 1, m, pos.r, f[pos.idx], g[pos.idx]);
T[1].upd(1, 1, m, pos.l, f[pos.idx], g[pos.idx]);
// cout << i << " " << pos.l << " " << pos.r << " ";
// cout << pos.idx << " " << f[pos.idx] << " " << g[pos.idx] << "\n";
}
}
cout << T[1].t[1].first << " " << T[1].t[1].second % mod << " ";
}
Compilation message
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
trapezoid.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19280 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19280 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
19280 KB |
Output isn't correct |
| 4 |
Correct |
15 ms |
19280 KB |
Output is correct |
| 5 |
Incorrect |
16 ms |
19536 KB |
Output isn't correct |
| 6 |
Incorrect |
21 ms |
20048 KB |
Output isn't correct |
| 7 |
Correct |
19 ms |
19836 KB |
Output is correct |
| 8 |
Incorrect |
24 ms |
20060 KB |
Output isn't correct |
| 9 |
Incorrect |
32 ms |
21532 KB |
Output isn't correct |
| 10 |
Correct |
50 ms |
23116 KB |
Output is correct |
| 11 |
Incorrect |
61 ms |
25288 KB |
Output isn't correct |
| 12 |
Incorrect |
109 ms |
30148 KB |
Output isn't correct |
| 13 |
Incorrect |
140 ms |
34260 KB |
Output isn't correct |
| 14 |
Incorrect |
174 ms |
40640 KB |
Output isn't correct |
| 15 |
Incorrect |
173 ms |
34888 KB |
Output isn't correct |
| 16 |
Incorrect |
204 ms |
36544 KB |
Output isn't correct |
| 17 |
Incorrect |
209 ms |
44064 KB |
Output isn't correct |
| 18 |
Correct |
181 ms |
37828 KB |
Output is correct |
| 19 |
Incorrect |
209 ms |
41408 KB |
Output isn't correct |
| 20 |
Incorrect |
235 ms |
43456 KB |
Output isn't correct |
