#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
const int MAXN = 100000, MOD = 30013;
//Global Variables
int N, A[MAXN], B[MAXN], C[MAXN], D[MAXN], AB[2*MAXN], dpmax[MAXN], dpcnt[MAXN], treemax[8*MAXN+1], treecnt[8*MAXN+1];
map<int, int> ab, cd;
pair<int, int> CD[2*MAXN];
void update (int ind, int L, int R, int x, int i) {
if (x < L || R < x) return;
if (L == R) {
treemax[ind] = dpmax[i];
treecnt[ind] = dpcnt[i];
return;
}
update(ind*2, L, (L+R)/2, x, i); update(ind*2+1, (L+R)/2+1, R, x, i);
if (treemax[ind*2] == treemax[ind*2+1]) {
treemax[ind] = treemax[ind*2];
treecnt[ind] = treecnt[ind*2]+treecnt[ind*2+1];
}
else if (treemax[ind*2] > treemax[ind*2+1]) {
treemax[ind] = treemax[ind*2];
treecnt[ind] = treecnt[ind*2];
}
else {
treemax[ind] = treemax[ind*2+1];
treecnt[ind] = treecnt[ind*2+1];
}
}
pair<int, int> query(int ind, int L, int R, int oL, int oR) { /// (max, cnt)
if (oL <= L && R <= oR) return mp(treemax[ind], treecnt[ind]);
if (R < oL || oR < L) return mp(0, 0);
pair<int, int> i = query(ind*2, L, (L+R)/2, oL, oR), j = query(ind*2+1, (L+R)/2+1, R, oL, oR);
if (i.a == j.a) return mp(i.a, i.b+j.b);
if (i.a < j.a) return j;
return i;
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi {
cin >> A[i] >> B[i] >> C[i] >> D[i];
AB[2*i] = A[i], AB[2*i+1] = B[i];
CD[2*i].a = C[i], CD[2*i+1].a = D[i];
CD[2*i].b = CD[2*i+1].b = i;
}
/// coordinate compress. new coordinates: 1 : 2*N
sort(AB, AB+2*N); sort(CD, CD+2*N);
For (i, 1, 2*N+1) {
ab[AB[i-1]] = i;
cd[CD[i-1].a] = i;
}
ffi {
A[i] = ab[A[i]]; B[i] = ab[B[i]]; C[i] = cd[C[i]]; D[i] = cd[D[i]];
//w<< i c A[i] s B[i] s C[i] s D[i]<<e;
}
For (j, 0, 2*N) {
int i = CD[j].b;
if (dpmax[i] == 0) {
/// we are at a C
pair<int, int> get = query(1, 1, 2*N, 1, A[i]); /// (max, cnt)
if (get.a == 0) get.b = 1;
dpmax[i] = get.a+1;
dpcnt[i] = get.b;
}
else {
/// we are at a D
update(1, 1, 2*N, B[i], i);
}
}
int out1 = 0, out2 =0;
ffi out1 = max(out1, dpmax[i]);
ffi if (dpmax[i] == out1) out2 += dpcnt[i];
w<< out1 s out2<<e;
}
Compilation message
trapezoid.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
532 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
4 ms |
760 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
6 ms |
1272 KB |
Partially correct |
| 6 |
Incorrect |
9 ms |
1784 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
14 ms |
2168 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
17 ms |
2680 KB |
Partially correct |
| 9 |
Incorrect |
36 ms |
5292 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Incorrect |
76 ms |
9884 KB |
Expected int32, but "-5022802232222890496" found |
| 11 |
Incorrect |
97 ms |
11672 KB |
Expected int32, but "-1298419000938405298" found |
| 12 |
Incorrect |
223 ms |
23032 KB |
Expected int32, but "9183932486774365824" found |
| 13 |
Incorrect |
252 ms |
26744 KB |
Expected int32, but "-4195152448689438272" found |
| 14 |
Incorrect |
333 ms |
34680 KB |
Expected int32, but "-3175106568905838848" found |
| 15 |
Incorrect |
363 ms |
36472 KB |
Expected int32, but "-8026369531311511552" found |
| 16 |
Incorrect |
410 ms |
38264 KB |
Expected int32, but "6233362917342126368" found |
| 17 |
Incorrect |
439 ms |
40440 KB |
Expected int32, but "-7505826292837535760" found |
| 18 |
Incorrect |
389 ms |
42088 KB |
Expected int32, but "-6197299359079266322" found |
| 19 |
Incorrect |
434 ms |
42872 KB |
Expected int32, but "5619696618904563712" found |
| 20 |
Execution timed out |
520 ms |
45432 KB |
Time limit exceeded |
