#include "bits/stdc++.h"
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
const int MN = 1e5 + 10, ME = 8 * MN, MOD = 30013;
struct node{int ma, cnt;};
node seg[ME];
node comb(const node a, const node b){
node ret = {max(a.ma, b.ma), 0};
if(a.ma == ret.ma) ret.cnt += a.cnt;
if(b.ma == ret.ma) ret.cnt += b.cnt;
ret.cnt %= MOD;
return ret;
}
void upd(int i, int to, int cnt, int v, int nl, int nr){
if(nl == nr){
seg[v] = {to, cnt};
} else {
int mid = (nl + nr) / 2;
if(i <= mid) upd(i,to,cnt, 2*v,nl,mid);
else upd(i,to,cnt, 2*v+1,mid+1,nr);
seg[v] = comb(seg[2*v], seg[2*v+1]);
}
}
node qu(int l, int r, int v, int nl, int nr){
if(nl > r || nr < l) return {0, 0};
else if(nl == l && nr == r) return seg[v];
else {
int mid = (nl + nr) / 2;
return comb(
qu(l, min(mid, r), 2*v, nl, mid),
qu(max(l, mid+1), r, 2*v+1, mid+1, nr)
);
}
}
struct trap{int a, b, c, d, ci, di;};
trap trp[MN];
struct ev{int ty, in, ti;}; // ty: 0->open, 1->close
int tma[MN], tc[MN];
signed main(){
int n; cin >> n;
set<int> bin;
vector<ev> evs;
forR(i, n) {
cin >> trp[i].a >> trp[i].b >> trp[i].c >> trp[i].d;
bin.insert(trp[i].c); bin.insert(trp[i].d);
evs.push_back({0, trp[i].a, i});
evs.push_back({1, trp[i].b, i});
}
vector<int> vbin; for(int i : bin) vbin.push_back(i);
forR(i, n){
trp[i].ci = lower_bound(all(vbin), trp[i].c) - vbin.begin() + 1;
trp[i].di = lower_bound(all(vbin), trp[i].d) - vbin.begin() + 1;
}
sort(all(evs), [](ev& a, ev& b){return a.in < b.in;});
int bs = vbin.size();
upd(0, 0, 1, 1, 0, bs);
for(auto [ty, in, ti] : evs){
if(ty == 0){
node ans = qu(0, trp[ti].ci-1, 1, 0, bs);
// printf("%d %d [%d, %d]\n", ty, ti, ans.ma, ans.cnt);
tma[ti] = ans.ma + 1; tc[ti] = ans.cnt;
} else {
// printf("%d %d [%d, %d]\n", ty, ti, tma[ti], tc[ti]);
upd(trp[ti].di, tma[ti], tc[ti], 1, 0, bs);
}
}
node ans = qu(0, bs, 1, 0, bs);
cout << ans.ma << ' ' << ans.cnt << '\n';
}
Compilation message
trapezoid.cpp: In function 'bool operator<(pii, pii)':
trapezoid.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
| ~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| 5 |
Correct |
4 ms |
724 KB |
Output is correct |
| 6 |
Correct |
6 ms |
980 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1128 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
22 ms |
2740 KB |
Output is correct |
| 10 |
Correct |
46 ms |
5220 KB |
Output is correct |
| 11 |
Correct |
55 ms |
6072 KB |
Output is correct |
| 12 |
Correct |
116 ms |
12028 KB |
Output is correct |
| 13 |
Correct |
145 ms |
13768 KB |
Output is correct |
| 14 |
Correct |
169 ms |
18252 KB |
Output is correct |
| 15 |
Correct |
188 ms |
19068 KB |
Output is correct |
| 16 |
Correct |
208 ms |
20040 KB |
Output is correct |
| 17 |
Correct |
209 ms |
21008 KB |
Output is correct |
| 18 |
Correct |
206 ms |
21768 KB |
Output is correct |
| 19 |
Correct |
217 ms |
22264 KB |
Output is correct |
| 20 |
Correct |
248 ms |
23560 KB |
Output is correct |
