Submission #1033215

#TimeUsernameProblemLanguageResultExecution timeMemory
1033215raphaelptrapezoid (balkan11_trapezoid)C++14
30 / 100
313 ms50024 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...