제출 #308457

#제출 시각아이디문제언어결과실행 시간메모리
308457andreiomdMatryoshka (JOI16_matryoshka)C++11
51 / 100
2083 ms14968 KiB
#include <iostream> #include <algorithm> using namespace std; const int NMAX = 2e5 + 1, QMAX = 2e5 + 1; const int TMAX = (NMAX + QMAX - 1); typedef pair < int, int > PII; typedef pair < int, PII > PIII; int N, Q; PII A[NMAX]; PIII Queries[QMAX]; int B[(TMAX << 1)], V[(TMAX << 1)]; int ans[QMAX]; static inline void Read () { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cin >> N >> Q; for(int i = 1; i <= N; ++i) { cin >> A[i].first >> A[i].second; B[++B[0]] = A[i].first, B[++B[0]] = A[i].second; } for(int i = 1; i <= Q; ++i) { cin >> Queries[i].second.first >> Queries[i].second.second, Queries[i].first = i; B[++B[0]] = Queries[i].second.first, B[++B[0]] = Queries[i].second.second; } return; } static inline int Find (int Val) { return (int)(lower_bound(V + 1, V + V[0] + 1, Val) - V); } static inline void Replace () { for(int i = 1; i <= N; ++i) A[i].first = Find(A[i].first), A[i].second = Find(A[i].second); for(int i = 1; i <= Q; ++i) Queries[i].second.first = Find(Queries[i].second.first), Queries[i].second.second = Find(Queries[i].second.second); return; } static inline void Normalize () { sort(B + 1, B + B[0] + 1); V[++V[0]] = B[1]; for(int i = 2; i <= B[0]; ++i) if(B[i] != B[i - 1]) V[++V[0]] = B[i]; Replace(); return; } auto cmp_1 = [] (PII A, PII B) { if(A.second < B.second) return 1; if(A.second > B.second) return 0; if(A.first > B.first) return 1; return 0; }; auto cmp_2 = [] (PIII A, PIII B) { if(A.second.second < B.second.second) return 1; return 0; }; static inline void Sort () { sort(A + 1, A + N + 1, cmp_1); sort(Queries + 1, Queries + Q + 1, cmp_2); return; } static inline void Solve () { int Last_Valid_Position = 0; int List[NMAX], l = 0; int Stack[NMAX], k = 0; for(int p = 1; p <= Q; ++p) { while(Last_Valid_Position < N && A[Last_Valid_Position + 1].second <= Queries[p].second.second) ++Last_Valid_Position; l = 0; for(int i = 1; i <= Last_Valid_Position; ++i) if(A[i].first >= Queries[p].second.first) List[++l] = A[i].first; k = 0; for(int i = 1; i <= l; ++i) { int X = List[i]; if(!k) Stack[++k] = X; else { int l = 1, r = k, pos = 0; while(l <= r) { int m = ((l + r) >> 1); if(X > Stack[m]) pos = m, r = m - 1; else l = m + 1; } if(!pos) Stack[++k] = X; else Stack[pos] = X; } } ans[Queries[p].first] = k; } return; } static inline void Write () { for(int i = 1; i <= Q; ++i) cout << ans[i] << '\n'; return; } int main() { Read(); Normalize(); Sort(); Solve(); Write(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...