| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 295804 | FlashGamezzz | trapezoid (balkan11_trapezoid) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
long n, dp[100005], inds[100005], inds2[100005], maxa[300000] = {}, maxa2[30013][300000];
void updf(long i, long s, long e, long v, long d) {
if (s > v || e < v) {
return;
}
if (s == e && s == v) {
maxa[i] = d;
return;
}
updf(i * 2 + 1, s, (s + e)/2, v, d);
updf(i * 2 + 2, (s + e)/2 + 1, e, v, d);
maxa[i] = max(maxa[i * 2 + 1], maxa[i * 2 + 2]);
}
void updh(long v, long d) {
long a = 0, b = 0;
updf(a, b, n-1, v, d);
}
long maxf(long i, long s, long e, long l, long u) {
if (s > e || s > u || e < l) {
return -1000;
}
if (s >= l && e <= u) {
return maxa[i];
}
return max(maxf(2*i+1, s, (s+e)/2, l, u), maxf(2*i+2, (s+e)/2+1, e, l, u));
}
long maxh(long l, long u) {
if (u < l){
return 0;
}
long a = 0, b = 0;
return maxf(a, b, n-1, l, u);
}
struct trap {
long a, b, c, d, i;
trap(long i1, long i2, long i3, long i4){
a = i1; b = i2; c = i3; d = i4; i = 0;
}
};
bool comp1 (trap t1, trap t2){
return t1.a < t2.a;
}
struct comp2 {
bool operator()(trap t1, trap t2){
return t1.b > t2.b;
}
};
struct comp3 {
bool operator()(trap t1, trap t2){
return t1.c > t2.c;
}
};
struct comp4 {
bool operator()(trap t1, trap t2){
return t1.d > t2.d;
}
};
vector<trap> pqa;
priority_queue<trap, vector<trap>, comp2> pqb;
priority_queue<trap, vector<trap>, comp3> pqc;
priority_queue<trap, vector<trap>, comp4> pqd;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (long i = 0; i < n; i++){
long i1, i2, i3, i4;
cin >> i1 >> i2 >> i3 >> i4;
pqa.push_back(trap(i1, i2, i3, i4));
}
sort(pqa.begin(), pqa.end(), comp1);
for (long i = 0; i < n; i++){
pqa[i].i = i; pqd.push(pqa[i]); pqc.push(pqa[i]);
}
for (long i = 0; i < n; i++){
inds[pqd.top().i] = i;
while (pqc.size() > 0 && pqc.top().c < pqd.top().d){
inds2[pqc.top().i] = i-1; pqc.pop();
}
pqd.pop();
}
long a1 = 0;
for (long i = 0; i < n; i++){
trap curr = pqa[i];
while (pqb.size() > 0 && pqb.top().b < curr.a){
updh(inds[pqb.top().i], dp[pqb.top().i]); pqb.pop();
}
pqb.push(curr);
dp[i] = maxh(0, inds2[curr.i])+1;
a1 = max(a1, dp[i]);
}
cout << a1 % 30013 << " " << 0 << endl;
}