#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e5 + 50;
const ll Mod = 30013;
ll n;
pll res[N], fen[N];
vector<pair<pii, pii>> vec;
vector<int> up, down;
vector<pii> qu[N][2], bit;
pii merg(pii a, pii b){
if(a.F > b.F) return a;
else if(a.F < b.F) return b;
else{
int sum = a.S + b.S;
if(sum >= Mod) sum -= Mod;
return {a.F, sum};
}
}
void upd(int x, pii y){
for(; x <= n; x += x & (-x)) fen[x] = merg(fen[x], y);
}
pii get(int x){
pii out = {0, 1};
for(; x; x -= x & (-x)) out = merg(out, fen[x]);
return out;
}
int main(){
fast_io;
cin >> n;
for(int i = 0; i < n; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
vec.pb({{a, b}, {c, d}});
up.pb(a); up.pb(b);
down.pb(c); down.pb(d);
}
sort(all(up));
up.resize(unique(all(up)) - up.begin());
sort(all(down));
down.resize(unique(all(down)) - down.begin());
bit.pb({0, 0});
for(int i = 0; i < n; i++){
vec[i].F.F = lower_bound(all(up), vec[i].F.F) - up.begin() + 1;
vec[i].F.S = lower_bound(all(up), vec[i].F.S) - up.begin() + 1;
vec[i].S.F = lower_bound(all(down), vec[i].S.F) - down.begin() + 1;
vec[i].S.S = lower_bound(all(down), vec[i].S.S) - down.begin() + 1;
qu[vec[i].F.F][0].pb({vec[i].S.F, i});
qu[vec[i].F.S][1].pb({vec[i].S.S, i});
bit.pb({vec[i].S.S, vec[i].F.S});
}
sort(all(bit));
for(int i = 0; i < N; i++){
for(auto [x, id]: qu[i][0]){
pii y = {x, 0};
int idx = lower_bound(all(bit), y) - bit.begin();
res[id] = get(idx - 1); res[id].F++;
}
for(auto [x, id]: qu[i][1]){
pii y = {x, i};
int idx = lower_bound(all(bit), y) - bit.begin();
upd(idx, res[id]);
}
}
pii ans = {0, 0};
for(int i = 0; i < n; i++) ans = merg(ans, res[i]);
cout << ans.F << sep << ans.S;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:90:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for(auto [x, id]: qu[i][0]){
| ^
trapezoid.cpp:95:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
95 | for(auto [x, id]: qu[i][1]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 6 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 7 |
Correct |
6 ms |
13404 KB |
Output is correct |
| 8 |
Correct |
8 ms |
13404 KB |
Output is correct |
| 9 |
Correct |
15 ms |
14192 KB |
Output is correct |
| 10 |
Correct |
23 ms |
15304 KB |
Output is correct |
| 11 |
Correct |
25 ms |
16080 KB |
Output is correct |
| 12 |
Correct |
51 ms |
19400 KB |
Output is correct |
| 13 |
Correct |
63 ms |
20672 KB |
Output is correct |
| 14 |
Correct |
86 ms |
22160 KB |
Output is correct |
| 15 |
Correct |
78 ms |
22720 KB |
Output is correct |
| 16 |
Correct |
91 ms |
23228 KB |
Output is correct |
| 17 |
Correct |
94 ms |
24204 KB |
Output is correct |
| 18 |
Correct |
84 ms |
24784 KB |
Output is correct |
| 19 |
Correct |
98 ms |
25540 KB |
Output is correct |
| 20 |
Correct |
114 ms |
26304 KB |
Output is correct |
