//#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<ll,ll> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
const int mod = 30013;
const ll oo = 5e18;
int n, a[N], b[N], c[N], d[N], mx = 1e6;
vector<int> open[N], close[N];
int st[N << 1], t[N << 1], f[N], g[N];
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;
for(int i = 1; i <= n; i ++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
open[a[i]].pb(i);
close[b[i] + 1].pb(i);
}
for(int i = 1; i <= 1e6; i ++){
for(auto j : close[i]){
update(d[j], f[j], g[j]);
// cerr << d[j] << " " << f[j] << " " << g[j] << " up\n";
}
for(auto j : open[i]){
auto kq = get(1, c[j] - 1);
f[j] = kq.fi + 1, g[j] = kq.se;
if(f[j] == 1) g[j] = 1;
// cerr << c[j] - 1 << " " << j << " " << f[j] << " " << g[j] << " y\n";
}
}
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:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
57940 KB |
Output is correct |
| 2 |
Correct |
16 ms |
57948 KB |
Output is correct |
| 3 |
Correct |
16 ms |
58112 KB |
Output is correct |
| 4 |
Correct |
16 ms |
57948 KB |
Output is correct |
| 5 |
Correct |
16 ms |
58460 KB |
Output is correct |
| 6 |
Correct |
22 ms |
59740 KB |
Output is correct |
| 7 |
Correct |
18 ms |
59228 KB |
Output is correct |
| 8 |
Correct |
19 ms |
58596 KB |
Output is correct |
| 9 |
Correct |
24 ms |
59228 KB |
Output is correct |
| 10 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Correct |
38 ms |
65536 KB |
Output is correct |
| 12 |
Runtime error |
42 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
42 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
88 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
55 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
56 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
55 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
57 ms |
65536 KB |
Execution killed with signal 9 |
