제출 #299403

#제출 시각아이디문제언어결과실행 시간메모리
299403FlashGamezzz사다리꼴 (balkan11_trapezoid)C++17
65 / 100
207 ms23668 KiB
#include <iostream> #include <cstdlib> #include <cstdio> #include <fstream> #include <algorithm> #include <string> #include <utility> #include <vector> #include <queue> #include <set> #include <map> #include <unordered_map> using namespace std; long n, dp[100005], dp2[100005], maxa[500000] = {}, suma[500000] = {}; void updf(long i, long s, long e, long v, long dm, long ds) { if (s > v || e < v) { return; } if (s == e && s == v) { maxa[i] = dm; suma[i] = ds; return; } updf(2*i+1, s, (s+e)/2, v, dm, ds); updf(2*i+2, (s+e)/2+1, e, v, dm, ds); if (maxa[2*i+1] > maxa[2*i+2]){ maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1]; } else if (maxa[2*i+1] == maxa[2*i+2]){ maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1]+suma[2*i+2] % 30013; } else { maxa[i] = maxa[2*i+2], suma[i] = suma[2*i+2]; } } void updh(long ind, long dm, long ds) { long a = 0, b = 0; updf(a, b, n-1, ind, dm, ds); } pair<long, long> qf(long i, long s, long e, long l, long u) { if (s > e || s > u || e < l) { return make_pair(-1000, 0); } if (s >= l && e <= u) { return make_pair(maxa[i], suma[i]); } pair<long, long> a = qf(2*i+1, s, (s+e)/2, l, u), b = qf(2*i+2, (s+e)/2+1, e, l, u); if (a.first > b.first){ return a; } else if (a.first < b.first){ return b; } else { return make_pair(a.first, a.second+b.second%30013); } } pair<long, long> qh(long l, long u) { long a = 0, b = 0; return qf(a, b, n-1, l, u); } struct trap { long a, b, c, d, i; trap(long i1, long i2, long i3, long i4){ a = i1; b = i2; c = i3; d = i4; i = 0; } }; bool comp1 (trap t1, trap t2){ return t1.a < t2.a; } struct comp2 { bool operator()(trap t1, trap t2){ return t1.b > t2.b; } }; vector<long> cc; unordered_map<long, long> ccm; vector<trap> pqa; priority_queue<trap, vector<trap>, comp2> pqb; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (long i = 0; i < n; i++){ long i1, i2, i3, i4; cin >> i1 >> i2 >> i3 >> i4; cc.push_back(i3); cc.push_back(i4); pqa.push_back(trap(i1, i2, i3, i4)); } sort(cc.begin(), cc.end()); for (int i = 0; i < 2*n; i++){ ccm.insert(make_pair(cc[i], i)); } sort(pqa.begin(), pqa.end(), comp1); for (long i = 0; i < n; i++){ pqa[i].i = i; pqa[i].c = ccm[pqa[i].c]+1; pqa[i].d = ccm[pqa[i].d]+1; } n = 2*n+1; updh(0, 0, 1); for (long i = 0; i < pqa.size(); i++){ while (pqb.size() > 0 && pqb.top().b < pqa[i].a){ updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop(); } pair<long, long> temp = qh(0, pqa[i].c); dp[i] = temp.first+1; dp2[i] = temp.second; pqb.push(pqa[i]); } while (pqb.size() > 0){ updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop(); } pair<long, long> ans = qh(0, n-1); cout << ans.first % 30013 << " " << ans.second % 30013 << endl; }

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (long i = 0; i < pqa.size(); i++){
      |                   ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...