#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 100005;
int N;
struct Segment {
int a, b, t;
Segment (int a = 0, int b = 0, int t = 0): a(a), b(b), t(t) { }
bool operator< (const Segment &s) const { return a != s.a ? a < s.a : b > s.b; }
};
Segment D[N_+N_];
int DN;
int X[N_+N_];
const int MOD = 30013;
const int LEAF = 131072*2;
struct Node {
int c, p;
Node (int c = 0, int p = 0): c(c), p(p) { }
void apply (Node t) {
if(t.c > c) c = t.c, p = t.p;
else if(t.c == c) p = (p + t.p) % MOD;
}
} Tree[N_+N_+LEAF], Table[N_];
void update (int x, int c, int p) {
x += LEAF;
if(Tree[x].c < c) Tree[x] = Node(c, p);
while(x >>= 1) {
Node &nd = Tree[x];
Node &l = Tree[x+x], &r = Tree[x+x+1];
if(l.c == r.c) nd = Node(l.c, (l.p + r.p) % MOD);
else if(l.c > r.c) nd = l;
else nd = r;
}
}
Node get (int en) {
int st = LEAF+1; en += LEAF;
Node ret;
while(st <= en) {
if((st & 1) == 1) ret.apply(Tree[st]);
if((en & 1) == 0) ret.apply(Tree[en]);
st = (st+1) >> 1;
en = (en-1) >> 1;
}
return ret;
}
int main() {
int i, j, k;
scanf("%d", &N);
for(i = 1; i <= N; i++) {
int a,b,c,d; scanf("%d%d%d%d", &a, &b, &c, &d);
D[++DN] = Segment(a, b, -i); X[DN] = b;
D[++DN] = Segment(c, d, i); X[DN] = d;
}
sort(D+1, D+DN+1);
sort(X+1, X+DN+1);
for(i = 1; i <= DN; i++) {
Segment &s = D[i];
s.b = lower_bound(X+1, X+DN+1, s.b) - X;
if(s.t < 0) { // left
Table[-s.t] = get(s.b - 1);
++Table[-s.t].c;
}else {
update(s.b, Table[s.t].c, Table[s.t].p);
}
}
printf("%d %d\n", get(DN).c, 0);
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:79:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k;
^
trapezoid.cpp:79:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
trapezoid.cpp:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
trapezoid.cpp:83:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a,b,c,d; scanf("%d%d%d%d", &a, &b, &c, &d);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8636 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
8636 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
8636 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
8636 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
8636 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
8636 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
8636 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
8636 KB |
Output isn't correct |
| 9 |
Partially correct |
13 ms |
8636 KB |
Partially correct |
| 10 |
Incorrect |
26 ms |
8636 KB |
Output isn't correct |
| 11 |
Incorrect |
33 ms |
8636 KB |
Output isn't correct |
| 12 |
Incorrect |
63 ms |
8636 KB |
Output isn't correct |
| 13 |
Incorrect |
76 ms |
8636 KB |
Output isn't correct |
| 14 |
Incorrect |
93 ms |
8636 KB |
Output isn't correct |
| 15 |
Incorrect |
106 ms |
8636 KB |
Output isn't correct |
| 16 |
Incorrect |
123 ms |
8636 KB |
Output isn't correct |
| 17 |
Incorrect |
116 ms |
8636 KB |
Output isn't correct |
| 18 |
Incorrect |
109 ms |
8636 KB |
Output isn't correct |
| 19 |
Incorrect |
119 ms |
8636 KB |
Output isn't correct |
| 20 |
Incorrect |
143 ms |
8636 KB |
Output isn't correct |
