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[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;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x19): relocation truncated to fit: R_X86_64_32S against symbol `std::ios_base::Init::_S_refcount' defined in .bss._ZNSt8ios_base4Init11_S_refcountE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x6b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x80): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x8b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xa0): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xab): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xba): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xcd): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xd4): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
