#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 524288
#define MOD 30013
inline int add(int a, int b){return (a+b>=MOD)?a+b-MOD:a+b;}
inline void inc(int& a, int b){a = add(a, b);}
inline int sub(int a, int b){return (a-b<0)?a-b+MOD:a-b;}
inline void dec(int &a, int b){a = sub(a, b);}
inline int mul(int a, int b){return 1ll*a*b%MOD;}
inline void grow(int &a, int b){a = mul(a, b);}
pair<int, int> tree[2*INF];
pair<int, int> merge(pair<int, int> a, pair<int, int> b){
if(a.first != b.first) return max(a, b);
return {a.first, add(a.second,b.second)};
}
void upd(int pos, int val, int cnt, int tl = 0, int tr = INF-1, int v = 1){
if(tl > pos || tr < pos) return;
if(tl == tr){
tree[v] = {val, cnt};
return;
}
int tm = (tl+tr)/2;
upd(pos, val, cnt, tl, tm, v*2);
upd(pos, val, cnt, tm+1, tr, v*2+1);
tree[v] = merge(tree[v*2], tree[v*2+1]);
}
pair<int, int> query(int l, int r, int tl = 0, int tr = INF-1, int v = 1){
if(tl > r || tr < l) return {0, 0};
if(l <= tl && tr <= r) return tree[v];
int tm = (tl+tr)/2;
return merge(query(l, r, tl, tm, v*2), query(l, r, tm+1, tr, v*2+1));
}
int n;
vector<int> coords;
map<int, int> mp;
pair<pair<int, int>, pair<int, int>> stuff[MAXN];
vector<pair<int, int>> ask[INF]; // y-coord, id
vector<pair<pair<int, int>, int>> todo[INF]; // val, y-coord
pair<int, int> ans = {0, 1};
int main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i<=n; i++){
int a, b, c, d; cin >> a >> b >> c >> d;
coords.push_back(a); coords.push_back(b); coords.push_back(c); coords.push_back(d);
stuff[i] = {{a, c}, {b, d}};
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
// for(auto x : coords) cout << x << endl;
for(int i = 0; i<coords.size(); i++) mp[coords[i]] = i+1;
for(int i = 1; i<=n; i++) stuff[i] = {{mp[stuff[i].first.first], mp[stuff[i].first.second]}, {mp[stuff[i].second.first], mp[stuff[i].second.second]}};
for(int i = 1; i<=n; i++) ask[stuff[i].first.first].push_back({stuff[i].first.second, i});
for(int i = 1; i<INF; i++){
for(auto x : ask[i]){
pair<int, int> tmp = query(0, x.first-1); tmp.first += 1; if(tmp.first == 1) tmp.second = 1;
ans = merge(ans, tmp);
todo[stuff[x.second].second.first].push_back({tmp, stuff[x.second].second.second});
}
for(auto x : todo[i]){
upd(x.second, x.first.first, x.first.second);
}
}
cout << ans.first << endl;
cout << ans.second << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i<coords.size(); i++) mp[coords[i]] = i+1;
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
25068 KB |
Output is correct |
| 2 |
Correct |
20 ms |
25036 KB |
Output is correct |
| 3 |
Correct |
23 ms |
25120 KB |
Output is correct |
| 4 |
Correct |
21 ms |
25196 KB |
Output is correct |
| 5 |
Correct |
25 ms |
25708 KB |
Output is correct |
| 6 |
Correct |
29 ms |
26092 KB |
Output is correct |
| 7 |
Correct |
31 ms |
25964 KB |
Output is correct |
| 8 |
Correct |
38 ms |
26476 KB |
Output is correct |
| 9 |
Correct |
53 ms |
28292 KB |
Output is correct |
| 10 |
Correct |
70 ms |
29932 KB |
Output is correct |
| 11 |
Correct |
101 ms |
33516 KB |
Output is correct |
| 12 |
Correct |
205 ms |
42088 KB |
Output is correct |
| 13 |
Correct |
232 ms |
45784 KB |
Output is correct |
| 14 |
Correct |
286 ms |
50276 KB |
Output is correct |
| 15 |
Correct |
296 ms |
48100 KB |
Output is correct |
| 16 |
Correct |
330 ms |
50148 KB |
Output is correct |
| 17 |
Correct |
363 ms |
54244 KB |
Output is correct |
| 18 |
Correct |
266 ms |
47076 KB |
Output is correct |
| 19 |
Correct |
386 ms |
56036 KB |
Output is correct |
| 20 |
Correct |
395 ms |
57260 KB |
Output is correct |
