# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
172769 | arnold518 | Matryoshka (JOI16_matryoshka) | C++14 | 262 ms | 8032 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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, p;
};
int N, Q, ans[MAXN+10];
Point A[MAXN+10];
vector<int> xcomp, ycomp;
int tree[MAXN*2+10];
void update(int i, int val) { for(; i<=xcomp.size(); i+=(i&-i)) tree[i]=max(tree[i], val); }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
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);
A[i].x*=-1; A[i].p=-1;
xcomp.push_back(A[i].x);
ycomp.push_back(A[i].y);
}
for(i=N+1; i<=N+Q; i++)
{
scanf("%d%d", &A[i].x, &A[i].y);
A[i].x*=-1; A[i].p=i-N;
xcomp.push_back(A[i].x);
ycomp.push_back(A[i].y);
}
sort(xcomp.begin(), xcomp.end());
sort(ycomp.begin(), ycomp.end());
xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
for(i=1; i<=N+Q; i++) A[i].x=lower_bound(xcomp.begin(), xcomp.end(), A[i].x)-xcomp.begin()+1;
for(i=1; i<=N+Q; i++) A[i].y=lower_bound(ycomp.begin(), ycomp.end(), A[i].y)-ycomp.begin()+1;
sort(A+1, A+N+Q+1, [&](const Point &p, const Point &q)
{
if(pii(p.y, p.x)!=pii(q.y, q.x)) return pii(p.y, p.x)<pii(q.y, q.x);
else return p.p<q.p;
});
for(i=1; i<=N+Q; i++)
{
if(A[i].p==-1) update(A[i].x, query(A[i].x)+1);
else ans[A[i].p]=query(A[i].x);
}
for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |