#include<bits/stdc++.h>
using namespace std;
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if(sizeof...(t)) cerr << ", ";
DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
void setIO(string NAME = "") {
cin.tie(0)->sync_with_stdio(0);
if(sz(NAME)) {
freopen((NAME + ".inp").c_str(),"r",stdin);
freopen((NAME + ".out").c_str(),"w",stdout);
}
}
const int MOD = 30013;
const int INF = 1e9+7;
int add(int a, int b) {
if((a += b) >= MOD) a-=MOD;
return a;
}
struct Tr {
int a,b,c,d;
bool operator<(const Tr& rhs) {
return a < rhs.a;
}
};
tcT> bool ckmax(T&a, const T&b) {
return b > a ? a = b, 1 : 0;
}
tcT> struct SegTree {
const T ID = {0,0}; T cmb(const T&a, const T&b) {
if(a.first == b.first) return {a.first, add(a.second, b.second) };
return a.first > b.first ? a : b;
}
int n; V<T> seg;
void init(int _n) {
for (n = 1; n < _n; ) n *= 2;
seg.assign(2*n,ID); }
void pull(int p) { seg[p] = cmb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) {
ckmax(seg[p += n], val) ; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) {
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = cmb(ra,seg[l++]);
if (r&1) rb = cmb(seg[--r],rb);
}
return cmb(ra,rb);
}
};
const int MX = 1e5+5;
int N;
SegTree<pi> st;
vi compr;
V<Tr> tr;
pi ans[MX];
pi res = {0, 1};
void solve() {
cin>>N;
F0R(i,N) {
int a, b, c, d;
cin>>a>>b>>c>>d;
tr.pb({a,b,c,d});
compr.pb(c); compr.pb(d);
}
N++;
tr.pb({INF-1, INF, INF-1, INF});
compr.pb(INF-1); compr.pb(INF);
sort(all(compr)); compr.erase(unique(all(compr)), compr.end());
F0R(i,N) {
tr[i].c = lower_bound(all(compr), tr[i].c) - compr.begin();
tr[i].d = lower_bound(all(compr), tr[i].d) - compr.begin();
}
sort(all(tr));
st.init(sz(compr));
pqg<pi> pq;
F0R(i,sz(tr)) {
while(sz(pq) && pq.top().first <= tr[i].a) {
int ind = pq.top().second;
st.upd(tr[ind].d, ans[ind]);
pq.pop();
}
pq.push({tr[i].b, i});
pi tmp = st.query(0, tr[i].c-1);
//dbg(tmp.first, tmp.second);
if(tmp.first == 0) ans[i] = {1, 1};
else ans[i] = {tmp.first+1, tmp.second};
}
cout << ans[sz(tr)-1].first-1 << " " << ans[sz(tr)-1].second << nl;
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
Compilation message
trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((NAME + ".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((NAME + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
600 KB |
Output is correct |
| 7 |
Correct |
4 ms |
596 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
20 ms |
2748 KB |
Output is correct |
| 11 |
Correct |
23 ms |
2896 KB |
Output is correct |
| 12 |
Correct |
54 ms |
4972 KB |
Output is correct |
| 13 |
Correct |
62 ms |
5208 KB |
Output is correct |
| 14 |
Correct |
71 ms |
8124 KB |
Output is correct |
| 15 |
Correct |
83 ms |
8252 KB |
Output is correct |
| 16 |
Correct |
87 ms |
8360 KB |
Output is correct |
| 17 |
Correct |
90 ms |
8632 KB |
Output is correct |
| 18 |
Correct |
85 ms |
8736 KB |
Output is correct |
| 19 |
Correct |
90 ms |
8928 KB |
Output is correct |
| 20 |
Correct |
99 ms |
9044 KB |
Output is correct |
