Submission #307812

#TimeUsernameProblemLanguageResultExecution timeMemory
307812andreiomdMatryoshka (JOI16_matryoshka)C++11
0 / 100
1 ms384 KiB
#include <iostream> #include <algorithm> using namespace std; typedef pair < int, int > PII; typedef pair < int, PII > Query; const int NMAX = 2e5 + 1, QMAX = 2e5 + 1; const int TMAX = (NMAX + QMAX); int N, Q; PII A[NMAX]; int B[(TMAX << 1)], V[(TMAX << 1)]; Query List[QMAX]; int ans[QMAX]; int dp[NMAX]; 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 >> List[i].second.first >> List[i].first, List[i].second.second = i; B[++B[0]] = List[i].second.first, B[++B[0]] = List[i].first; } 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) V[++V[0]] = B[i]; return; } auto cmp = [] (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; }; static inline void Sort () { sort(A + 1, A + N + 1, cmp); sort(List + 1, List + Q + 1); return; } static inline int my_max (int a, int b) { return ((a > b) ? a : b); } static inline void Solve () { Sort(); int Last_Valid_Position = 0; for(int i = 1; i <= Q; ++i) { while(Last_Valid_Position < N && A[Last_Valid_Position + 1].second <= List[i].first) { ++Last_Valid_Position; dp[Last_Valid_Position] = 1; for(int j = 1; j < Last_Valid_Position; ++j) if(A[j].first >= A[Last_Valid_Position].first) dp[Last_Valid_Position] = my_max(dp[Last_Valid_Position], dp[j] + 1); } int cnt = 0, Max = 0; for(int j = 1; j <= Last_Valid_Position; ++j) if(A[j].first >= List[i].second.first) ++cnt, Max = my_max(Max, dp[j]); ans[List[i].second.second] = cnt - Max; } for(int i = 1; i <= Q; ++i) cout << ans[i] << '\n'; return; } int main() { Read(); Normalize(); Solve(); 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...