#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])%MOD;
}
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)%MOD);
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]; out2 %= MOD;}
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 |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
5 ms |
888 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
11 ms |
1532 KB |
Output is correct |
| 8 |
Correct |
14 ms |
1784 KB |
Output is correct |
| 9 |
Correct |
27 ms |
3324 KB |
Output is correct |
| 10 |
Correct |
54 ms |
6080 KB |
Output is correct |
| 11 |
Correct |
73 ms |
7288 KB |
Output is correct |
| 12 |
Correct |
203 ms |
14236 KB |
Output is correct |
| 13 |
Correct |
237 ms |
16504 KB |
Output is correct |
| 14 |
Correct |
271 ms |
20980 KB |
Output is correct |
| 15 |
Correct |
342 ms |
22136 KB |
Output is correct |
| 16 |
Correct |
360 ms |
23160 KB |
Output is correct |
| 17 |
Correct |
365 ms |
24460 KB |
Output is correct |
| 18 |
Correct |
294 ms |
25596 KB |
Output is correct |
| 19 |
Correct |
363 ms |
26488 KB |
Output is correct |
| 20 |
Correct |
460 ms |
27912 KB |
Output is correct |
