//#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;
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};
}
typedef tuple<int,int,int,int,int> op;
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, ah;
vector<op> ver;
for(int i = 1; i <= n; i ++){
int a, b, c, d; cin >> a >> b >> c >> d;
ver.push_back({i, a, b + 1, c, d});
rrh.push_back(c);
rrh.push_back(d);
ah.push_back(a);
ah.push_back(b + 1);
}
mx = rrh.size();
sort(all(rrh));
rrh.resize(unique(all(rrh)) - rrh.begin());
st.push_back(0), t.push_back(0);
for(auto j : rrh) st.push_back(0), st.push_back(0), t.push_back(0), t.push_back(0);
int d = ah.size();
vector<vector<pii>> open(d + 2), close(d + 2);
sort(all(ah)); ah.resize(unique(all(ah)) - ah.begin());
for(auto [id, a, b, c, d] : ver){
a = lower_bound(all(ah), a) - ah.begin() + 1;
b = lower_bound(all(ah), b) - ah.begin() + 1;
// for(auto j : open[0]) cout << j << " \n";
open[a].push_back({id, c});
close[b].push_back({id, d});
}
for(int i = 1; i <= d; 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:78:14: warning: unused variable 'j' [-Wunused-variable]
78 | for(auto j : rrh) st.push_back(0), st.push_back(0), t.push_back(0), t.push_back(0);
| ^
trapezoid.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
860 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1188 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1368 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1628 KB |
Output is correct |
| 9 |
Correct |
11 ms |
2804 KB |
Output is correct |
| 10 |
Correct |
20 ms |
5200 KB |
Output is correct |
| 11 |
Correct |
27 ms |
6256 KB |
Output is correct |
| 12 |
Correct |
59 ms |
11916 KB |
Output is correct |
| 13 |
Correct |
73 ms |
14152 KB |
Output is correct |
| 14 |
Correct |
94 ms |
21224 KB |
Output is correct |
| 15 |
Correct |
97 ms |
19936 KB |
Output is correct |
| 16 |
Correct |
111 ms |
20440 KB |
Output is correct |
| 17 |
Correct |
112 ms |
21008 KB |
Output is correct |
| 18 |
Correct |
112 ms |
21988 KB |
Output is correct |
| 19 |
Correct |
121 ms |
23520 KB |
Output is correct |
| 20 |
Correct |
133 ms |
24280 KB |
Output is correct |
