#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 All{
public:
pii all[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(ll node, ll st, ll dr, ll a, pii b){
if(st == dr){
b.second %= MOD;
all[node] = b;
return;
}
ll mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b);
}else{
update(node * 2 + 1, mid + 1, dr, a, b);
}
all[node] = combine(all[node * 2], all[node * 2 + 1]);
}
pii query(ll node, ll st, ll dr, ll a, ll b){
if(a <= st && dr <= b){
return all[node];
}
ll 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(ll a, pii b){
update(1, 1, NMAX - 1, a, b);
}
pii prefix(ll x){
return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
}
}st;
struct ura{
ll a, b, c, d;
};
bool cmp(ura a, ura b){
return a.a < b.a;
}
pii dp[400001];
ura v[400001];
vector <ll> nrm;
map <ll, ll> mp;
int main() {
ll 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
ll 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:94:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(i = 0; i < nrm.size(); i++){
| ~~^~~~~~~~~~~~
trapezoid.cpp:108:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(i = 0; i < nrm.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
7 ms |
928 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1484 KB |
Output is correct |
| 8 |
Correct |
17 ms |
1740 KB |
Output is correct |
| 9 |
Correct |
34 ms |
2992 KB |
Output is correct |
| 10 |
Correct |
73 ms |
5692 KB |
Output is correct |
| 11 |
Correct |
93 ms |
6856 KB |
Output is correct |
| 12 |
Correct |
202 ms |
13780 KB |
Output is correct |
| 13 |
Correct |
248 ms |
16640 KB |
Output is correct |
| 14 |
Correct |
296 ms |
19132 KB |
Output is correct |
| 15 |
Correct |
352 ms |
20508 KB |
Output is correct |
| 16 |
Correct |
356 ms |
21932 KB |
Output is correct |
| 17 |
Correct |
409 ms |
23188 KB |
Output is correct |
| 18 |
Correct |
369 ms |
24372 KB |
Output is correct |
| 19 |
Correct |
451 ms |
24504 KB |
Output is correct |
| 20 |
Correct |
450 ms |
26732 KB |
Output is correct |
