#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 400001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
class AINT{
public:
pii aint[4 * NMAX];
pii combine(pii a, pii b){
if(a.first > b.first)
return a;
if(a.first < b.first)
return b;
return {a.first, (a.second + b.second) % MOD};
}
void update(int node, int st, int dr, int a, pii b){
if(st == dr){
aint[node] = b;
return;
}
int mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b);
}else{
update(node * 2 + 1, mid + 1, dr, a, b);
}
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
pii query(int node, int st, int dr, int a, int b){
if(a <= st && dr <= b){
return aint[node];
}
int mid = (st + dr) / 2;
pii rez = {-1, 0};
if(a <= mid){
rez = combine(rez, query(node * 2, st, mid, a, b));
}
if(b > mid){
rez = combine(rez, query(node * 2 + 1, mid + 1, dr, a, b));
}
return rez;
}
void set(int a, pii b){
update(1, 1, NMAX - 1, a, b);
}
pii prefix(int x){
return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
}
}st;
struct ura{
int a, b, c, d;
};
bool cmp(ura a, ura b){
return a.a < b.a;
}
pii dp[100001];
ura v[100001];
vector <int> nrm;
map <int, int> mp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, i;
cin >> n;
for(i = 1; i <= n; i++){
cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
nrm.push_back(v[i].a);
nrm.push_back(v[i].b);
}
///normalizare
int cnt = 0;
sort(nrm.begin(), nrm.end());
for(i = 0; i < nrm.size(); i++){
if(i == 0 || nrm[i] != nrm[i - 1])
cnt++;
mp[nrm[i]] = cnt;
}
nrm.clear();
for(i = 1; i <= n; i++){
v[i].a = mp[v[i].a];
v[i].b = mp[v[i].b];
nrm.push_back(v[i].c);
nrm.push_back(v[i].d);
}
mp.clear();
sort(nrm.begin(), nrm.end());
for(i = 0; i < nrm.size(); i++){
if(i == 0 || nrm[i] != nrm[i - 1])
cnt++;
mp[nrm[i]] = cnt;
}
nrm.clear();
for(i = 1; i <= n; i++){
v[i].c = mp[v[i].c];
v[i].d = mp[v[i].d];
}
mp.clear();
///gata
sort(v + 1, v + n + 1, cmp);
priority_queue <pii> pq; ///daca sortez dupa b, scot logul
pii sol = {0, 0};
st.set(1, {0, 1});
for(i = 1; i <= n; i++){
while(pq.size() && (-pq.top().first) <= v[i].a){
st.set(v[pq.top().second].d, dp[pq.top().second]);
pq.pop();
}
dp[i] = st.prefix(v[i].c);
dp[i].first++;
pq.push({-v[i].b, i});
sol = st.combine(sol, dp[i]);
}
cout << sol.first << " " << sol.second << "\n";
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(i = 0; i < nrm.size(); i++){
| ~~^~~~~~~~~~~~
trapezoid.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(i = 0; i < nrm.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
592 KB |
Output is correct |
| 5 |
Correct |
5 ms |
844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
972 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1228 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1384 KB |
Output is correct |
| 9 |
Correct |
30 ms |
2500 KB |
Output is correct |
| 10 |
Correct |
50 ms |
4700 KB |
Output is correct |
| 11 |
Correct |
62 ms |
5504 KB |
Output is correct |
| 12 |
Correct |
140 ms |
11148 KB |
Output is correct |
| 13 |
Correct |
177 ms |
13264 KB |
Output is correct |
| 14 |
Correct |
227 ms |
15292 KB |
Output is correct |
| 15 |
Correct |
233 ms |
16448 KB |
Output is correct |
| 16 |
Correct |
256 ms |
17468 KB |
Output is correct |
| 17 |
Correct |
256 ms |
18564 KB |
Output is correct |
| 18 |
Correct |
243 ms |
19392 KB |
Output is correct |
| 19 |
Correct |
272 ms |
19292 KB |
Output is correct |
| 20 |
Correct |
349 ms |
21216 KB |
Output is correct |
