Submission #172749

#TimeUsernameProblemLanguageResultExecution timeMemory
172749arnold518Matryoshka (JOI16_matryoshka)C++14
11 / 100
2 ms504 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; struct Point { int x, y; }; int N, Q; Point A[MAXN+10]; int main() { int i, j; scanf("%d%d", &N, &Q); for(i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y); sort(A+1, A+N+1, [&](const Point &p, const Point &q) { if(p.x!=q.x) return p.x<q.x; return p.y<q.y; }); vector<Point> V; multimap<int, int> S; for(i=1; i<=N; ) { for(j=i; j<=N && A[j].x==A[i].x; j++) { auto it = S.lower_bound(A[j].y); if(it==S.begin()) continue; it--; V.push_back({it->second, A[j].y}); S.erase(it); } for(j=i; j<=N && A[j].x==A[i].x; j++) { S.insert(pii(A[j].y, A[j].x)); } i=j; } while(Q--) { int a, b; scanf("%d%d", &a, &b); int ans=0; for(j=1; j<=N; j++) if(A[j].x>=a && A[j].y<=b) ans++; for(j=0; j<V.size(); j++) if(V[j].x>=a && V[j].y<=b) ans--; printf("%d\n", ans); } }

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<V.size(); j++) if(V[j].x>=a && V[j].y<=b) ans--;
                  ~^~~~~~~~~
matryoshka.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:23:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...