#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
vector<long long> st, count;
long long N;
long long l(long long x) { return (x << 1); }
long long r(long long x) { return (x << 1) + 1; }
void update(long long L, long long R, long long a, long long val, long long c, long long x)
{
if (L > a || R < a)
return;
if (L == a && R == a)
{
st[x] = val;
count[x] = c;
}
else
{
long long m = (L + R) / 2;
update(L, m, a, val, c, l(x));
update(m + 1, R, a, val, c, r(x));
st[x] = max(st[l(x)], st[r(x)]);
count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
}
}
pair<long long, long long> RSQ(long long L, long long R, long long a, long long b, long long x)
{
if (L > b || R < a)
return {0, 0};
if (L >= a && R <= b)
return {st[x], count[x]};
long long m = (L + R) / 2;
pair<long long, long long> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
if (temp1.first < temp2.first)
swap(temp1, temp2);
if (temp1.first == temp2.first)
temp1.second += temp2.second;
return temp1;
}
public:
SegTree(long long x)
{
N = pow(2, ceil(log2(x)));
st.assign(2 * N, 0);
count.assign(2 * N, 0);
}
void update(long long x, long long val, long long c) { update(0, N - 1, x, val, c, 1); }
pair<long long, long long> RSQ(long long a, long long b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
long long N;
cin >> N;
vector<vector<long long>> Tab;
vector<long long> vals;
for (long long i = 0; i < N; i++)
{
long long a, b, c, d;
cin >> a >> b >> c >> d;
vals.push_back(a), vals.push_back(b), vals.push_back(c), vals.push_back(d);
Tab.push_back({a, c, b, d});
}
sort(vals.begin(), vals.end());
sort(Tab.begin(), Tab.end());
map<long long, long long> M;
for (long long i = 0; i < vals.size(); i++)
{
M[vals[i]] = i;
}
for (long long i = 0; i < N; i++)
{
for (long long j = 0; j < 4; j++)
Tab[i][j] = M[Tab[i][j]];
}
SegTree ST(4 * N);
priority_queue<vector<long long>> PQ;
vector<pair<long long, long long>> ans(N);
pair<long long, long long> ans2 = {0, 0};
for (long long i = 0; i < N; i++)
{
while (!PQ.empty() && -PQ.top()[0] < Tab[i][0])
{
ST.update(PQ.top()[1], PQ.top()[2], PQ.top()[3]);
PQ.pop();
}
ans[i] = ST.RSQ(0, Tab[i][1]);
ans[i].first++;
if (ans[i].first == 1)
ans[i].second++;
ans[i].second = ans[i].second % 30013;
PQ.push({-Tab[i][2], Tab[i][3], ans[i].first, ans[i].second});
if (ans[i].first > ans2.first)
ans2 = {ans[i].first, 0};
if (ans[i].first == ans2.first)
ans2.second += ans[i].second;
ans2.second = ans2.second % 30013;
}
cout << ans2.first << ' ' << ans2.second;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:69:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (long long i = 0; i < vals.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
600 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1884 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3032 KB |
Output is correct |
| 9 |
Correct |
26 ms |
6152 KB |
Output is correct |
| 10 |
Correct |
42 ms |
10116 KB |
Output is correct |
| 11 |
Correct |
67 ms |
13696 KB |
Output is correct |
| 12 |
Correct |
147 ms |
27644 KB |
Output is correct |
| 13 |
Correct |
188 ms |
30076 KB |
Output is correct |
| 14 |
Correct |
257 ms |
43320 KB |
Output is correct |
| 15 |
Correct |
259 ms |
41664 KB |
Output is correct |
| 16 |
Correct |
321 ms |
42844 KB |
Output is correct |
| 17 |
Correct |
297 ms |
47844 KB |
Output is correct |
| 18 |
Correct |
216 ms |
38908 KB |
Output is correct |
| 19 |
Correct |
316 ms |
48744 KB |
Output is correct |
| 20 |
Correct |
334 ms |
50792 KB |
Output is correct |
