//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int mod = 30013;
//const ll oo = 5e18;
int n, mx = 0;
vector<pii> open[M], close[M];
int f[N], g[N];
vector<int> st, t;
void update(int i,int x,int cnt){
i += mx - 1;
if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod;
while(i > 1){
i /= 2;
if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod;
}
}
pii get(int l,int r){
r++;
int ret = 0, cnt = 0;
for(l += mx - 1, r += mx - 1; l < r; l /= 2, r /= 2){
if(l & 1){
if(ret < st[l]) ret = st[l], cnt = t[l];
else if(ret == st[l]) cnt = (cnt + t[l]) % mod;
l++;
}
if(r & 1){
--r;
if(ret < st[r]) ret = st[r], cnt = t[r];
else if(ret == st[r]) cnt = (cnt + t[r]) % mod;
}
}
return {ret, cnt};
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n;
vector<int> rrh;
for(int i = 1; i <= n; i ++){
int a, b, c, d; cin >> a >> b >> c >> d;
open[a].pb({i, c});
close[b + 1].pb({i, d});
rrh.pb(c);
rrh.pb(d);
}
mx = rrh.size();
sort(all(rrh));
rrh.resize(unique(all(rrh)) - rrh.begin());
st.pb(0), t.pb(0);
for(auto j : rrh) st.pb(0), st.pb(0), t.pb(0), t.pb(0);
for(int i = 1; i <= 1e6; i ++){
for(auto [id, j] : close[i]) update(lower_bound(all(rrh), j) - rrh.begin() + 1, f[id], g[id]);
close[i].clear();
for(auto [id, j] : open[i]){
auto kq = get(1, lower_bound(all(rrh), j) - rrh.begin());
f[id] = kq.fi + 1, g[id] = kq.se;
if(f[id] == 1) g[id] = 1;
}
open[i].clear();
}
int ans = 0, cnt = 0;
for(int i = 1; i <= n; i ++) if(ans < f[i]) ans = f[i], cnt = g[i]; else if(ans == f[i]) cnt = (cnt + g[i]) % mod;
cout << ans << " " << cnt;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:76:14: warning: unused variable 'j' [-Wunused-variable]
76 | for(auto j : rrh) st.pb(0), st.pb(0), t.pb(0), t.pb(0);
| ^
trapezoid.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
47960 KB |
Output is correct |
| 2 |
Correct |
14 ms |
47964 KB |
Output is correct |
| 3 |
Correct |
15 ms |
47964 KB |
Output is correct |
| 4 |
Correct |
16 ms |
47980 KB |
Output is correct |
| 5 |
Correct |
17 ms |
48220 KB |
Output is correct |
| 6 |
Correct |
17 ms |
48216 KB |
Output is correct |
| 7 |
Correct |
18 ms |
48472 KB |
Output is correct |
| 8 |
Correct |
19 ms |
48476 KB |
Output is correct |
| 9 |
Correct |
24 ms |
49112 KB |
Output is correct |
| 10 |
Correct |
34 ms |
50196 KB |
Output is correct |
| 11 |
Correct |
39 ms |
50816 KB |
Output is correct |
| 12 |
Correct |
77 ms |
54132 KB |
Output is correct |
| 13 |
Correct |
80 ms |
54984 KB |
Output is correct |
| 14 |
Runtime error |
150 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Correct |
107 ms |
56400 KB |
Output is correct |
| 16 |
Correct |
109 ms |
56792 KB |
Output is correct |
| 17 |
Correct |
115 ms |
59376 KB |
Output is correct |
| 18 |
Correct |
95 ms |
57484 KB |
Output is correct |
| 19 |
Correct |
121 ms |
59120 KB |
Output is correct |
| 20 |
Correct |
141 ms |
60180 KB |
Output is correct |
