# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
673138 | kirakaminski968 | trapezoid (balkan11_trapezoid) | C++17 | 136 ms | 17088 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int MX = 400042;
const int MOD = 30013;
int n;
pair<int, ll> bit[MX];
struct Trap {
int topL;
int topR;
int botL;
int botR;
bool operator<(const Trap& other) const {
return topL < other.topL;
}
} ls[100042];
int trapId[MX];
pair<int, ll> toSet[MX];
void add(int idx, pair<int, ll> val) {
for (++idx; idx < MX; idx += (idx & -idx)) {
if (bit[idx].fi == val.fi)
bit[idx].se = (bit[idx].se + val.se) % MOD;
else if (bit[idx].fi < val.fi)
bit[idx].se = val.se % MOD;
bit[idx].fi = max(bit[idx].fi, val.fi);
}
}
pair<int, ll> query(int idx) {
pair<int, int> ans {-1, 0};
for (++idx; idx > 0; idx -= (idx & -idx)) {
if (bit[idx].fi == ans.fi)
ans.se = (ans.se + bit[idx].se) % MOD;
else if (bit[idx].fi > ans.fi)
ans.se = bit[idx].se;
ans.fi = max(ans.fi, bit[idx].fi);
}
return ans;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
memset(trapId, -1, sizeof(trapId));
vector<int> coords {};
for (int i = 0; i < n; i++) {
cin >> ls[i].topL >> ls[i].topR >> ls[i].botL >> ls[i].botR;
coords.push_back(ls[i].topL);
coords.push_back(ls[i].topR);
coords.push_back(ls[i].botL);
coords.push_back(ls[i].botR);
}
ls[n] = {0, 0, 0, 0};
ls[n + 1] = {(int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1};
coords.push_back(0);
coords.push_back(1e9 + 1);
sort(coords.begin(), coords.end());
coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
for (int i = 0; i <= n + 1; i++) {
ls[i].topL = lower_bound(coords.begin(), coords.end(), ls[i].topL) - coords.begin();
ls[i].topR = lower_bound(coords.begin(), coords.end(), ls[i].topR) - coords.begin();
ls[i].botL = lower_bound(coords.begin(), coords.end(), ls[i].botL) - coords.begin();
ls[i].botR = lower_bound(coords.begin(), coords.end(), ls[i].botR) - coords.begin();
trapId[ls[i].topL] = i;
trapId[ls[i].topR] = i;
}
add(0, {1, 1});
for (int i = 1; i < (int)coords.size(); i++) {
if (trapId[i] != -1) {
int id = trapId[i];
auto cur = ls[id];
if (i == cur.topL) {
auto dpVal = query(cur.botL);
dpVal.first++;
toSet[cur.topR] = dpVal;
}
if (i == cur.topR) {
add(cur.botR, toSet[cur.topR]);
}
}
}
auto bst = query(MX - 2);
cout << bst.fi - 2 << ' ' << (bst.se % MOD) << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |