# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
295796 | FlashGamezzz | trapezoid (balkan11_trapezoid) | C++14 | 182 ms | 16692 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 <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[210000] = {};
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |