# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42572 | nonocut | Adriatic (CEOI13_adriatic) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxv = 2500;
const int maxn = 250000 + 5;
struct node {
int x,y,id;
};
int n;
node p[maxn];
int pos[maxv+5];
vector<int> way[maxn];
bool cmp(node a, node b) {
if(a.x!=b.x) return a.x<b.x;
return a.y>b.y;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y), p[i].id = i;
sort(&p[1],&p[n+1],cmp);
for(int i=1;i<=n;i++) {
int cur = 0;
for(int y=p[i].y-1;y>=1;y--) {
if(pos[y]>cur) {
cur = pos[y];
way[p[i].id].push_back(p[pos[y]].i);
}
}
pos[p[i].y] = i;
}
}