#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
const int N = 1e5 + 5;
const int mod = 30013;
const int inf = 1e9;
#define ul first.first
#define ur first.second
#define dl second.first
#define dr second.second
pair <ii,ii> a[N];
int n;
ii ans,dp[N],tree[N << 3];
map <int,int> ind;
vector <int> v,updates[N];
int add(int x,int y) {
return x + y >= mod ? x + y - mod : x + y;
}
ii merge(ii x,ii y) {
if (x.first == y.first)
return {x.first,add(x.second,y.second)};
if (x.first > y.first)
return x;
return y;
}
ii query(int ind,int l,int r,int lw,int rw) {
if (l > rw || r < lw)
return {-inf,-inf};
if (l >= lw && r <= rw)
return tree[ind];
int mid = (l + r) / 2;
return merge(query(ind + ind,l,mid,lw,rw),query(ind + ind + 1,mid + 1,r,lw,rw));
}
void update(int ind,int l,int r,int w,ii val) {
if (l > w || r < w)
return;
if (l == w && r == w) {
tree[ind] = merge(tree[ind],val);
return;
}
int mid = (l + r) / 2;
update(ind + ind,l,mid,w,val);
update(ind + ind + 1,mid + 1,r,w,val);
tree[ind] = merge(tree[ind + ind],tree[ind + ind + 1]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
v.push_back(a[i].dl);
v.push_back(a[i].dr);
}
sort(v.begin(),v.end());
for (int i = 0 , j = 0 ; i < v.size() ; i++) {
if (i == 0 || v[i] != v[i - 1])
j++;
ind[v[i]] = j;
}
sort(a + 1,a + n + 1);
for (int i = 1 ; i < (N << 3) ; i++)
tree[i] = {-inf,-inf};
for (int i = n , j = n ; i >= 1 ; i--) {
for (auto k : updates[i])
update(1,1,2 * n,ind[a[k].dl],dp[k]);
dp[i] = {1,1};
ii tut = query(1,1,2 * n,ind[a[i].dr],2 * n);
tut.first++;
dp[i] = merge(dp[i],tut);
while(j > 0 && a[j].ur >= a[i].ul)
j--;
ans = merge(ans,dp[i]);
updates[j].push_back(i);
}
cout << ans.first << " " << ans.second << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:67:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0 , j = 0 ; i < v.size() ; i++) {
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9088 KB |
Output is correct |
2 |
Correct |
9 ms |
8960 KB |
Output is correct |
3 |
Incorrect |
10 ms |
8960 KB |
Output isn't correct |
4 |
Correct |
10 ms |
9088 KB |
Output is correct |
5 |
Incorrect |
12 ms |
9216 KB |
Output isn't correct |
6 |
Incorrect |
15 ms |
9316 KB |
Output isn't correct |
7 |
Correct |
19 ms |
9472 KB |
Output is correct |
8 |
Incorrect |
16 ms |
9600 KB |
Output isn't correct |
9 |
Incorrect |
29 ms |
10368 KB |
Output isn't correct |
10 |
Correct |
48 ms |
11640 KB |
Output is correct |
11 |
Incorrect |
60 ms |
12280 KB |
Output isn't correct |
12 |
Incorrect |
111 ms |
15600 KB |
Output isn't correct |
13 |
Incorrect |
141 ms |
16884 KB |
Output isn't correct |
14 |
Incorrect |
187 ms |
18160 KB |
Output isn't correct |
15 |
Incorrect |
203 ms |
18796 KB |
Output isn't correct |
16 |
Incorrect |
229 ms |
19460 KB |
Output isn't correct |
17 |
Incorrect |
224 ms |
20200 KB |
Output isn't correct |
18 |
Correct |
187 ms |
20892 KB |
Output is correct |
19 |
Incorrect |
220 ms |
21408 KB |
Output isn't correct |
20 |
Incorrect |
257 ms |
22000 KB |
Output isn't correct |