#include<bits/stdc++.h>
using namespace std;
struct trap{
int a,b,c,d;
bool operator < (trap C) {
return a==C.a?b==C.b?c==C.c?d<C.d:c<C.c:b<C.b:a<C.a;
}
} t[200100];
map<int, int> mp;
struct make{
int v = 0, cnt = 0;
} tre[200100], ans[200100];
make operator + (make a, make b) {
make c;
c.cnt = a.cnt;
c.v = a.v;
if(b.v>a.v)
c.v = b.v,c.cnt=0;
if(b.v==c.v)
c.cnt+=b.cnt;
c.cnt%=30013;
return c;
}
void upd(make x, int p) {
while(p<200100)
tre[p] = tre[p] + x, p+=p&-p;
}
void Upd(int p, int up) {
while(p)
ans[up]=ans[up]+tre[p],p-=p&-p;
}
void clear(int x) {
while(x<200100)
tre[x] = {0,0}, x+=x&-x;
}
void cdq(int l, int r) {
if(l==r) {
ans[l].v++;
return;
}
int mid = l+r>>1;
cdq(l, mid);
vector<tuple<int, int, int>> tp;
for(int i = l; i <= mid; i++)
tp.push_back({t[i].b, t[i].d, i});
for(int j = mid+1; j <= r; j++)
tp.push_back({t[j].a, t[j].c, j});
sort(tp.begin(), tp.end());
for(auto i: tp) {
int a, b, c;
tie(a,b,c) = i;
if(c<=mid)
upd(ans[c],b);
else
Upd(b,c);
}
for(int i = l; i <= mid; i++)
clear(t[i].d);
tp.clear();
cdq(mid+1, r);
}
int main() {
for(int i = 0; i < 200100; i++)
ans[i].cnt=1;
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d,mp[t[i].d],
mp[t[i].a], mp[t[i].c], mp[t[i].b];
int x = 0;
for(auto &i: mp)
i.second=++x;
for(int i = 0; i < n; i++)
t[i].a=mp[t[i].a], t[i].b = mp[t[i].b], t[i].c = mp[t[i].c], t[i].d = mp[t[i].d];
sort(t, t+n);
cdq(0,n-1);
for(int i = 0; i < n; i++)
ans[n]=ans[n]+ans[i], cerr << ans[i].v << ' ' << ans[i].cnt << '\n';
cout << ans[n].v << ' ' << ans[n].cnt << '\n';
}
Compilation message
trapezoid.cpp: In function 'void cdq(int, int)':
trapezoid.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
4 ms |
2008 KB |
Output is correct |
4 |
Correct |
7 ms |
2004 KB |
Output is correct |
5 |
Correct |
13 ms |
2376 KB |
Output is correct |
6 |
Correct |
20 ms |
2680 KB |
Output is correct |
7 |
Correct |
26 ms |
2492 KB |
Output is correct |
8 |
Correct |
34 ms |
2908 KB |
Output is correct |
9 |
Correct |
69 ms |
4172 KB |
Output is correct |
10 |
Correct |
135 ms |
4956 KB |
Output is correct |
11 |
Correct |
175 ms |
7816 KB |
Output is correct |
12 |
Correct |
369 ms |
13756 KB |
Output is correct |
13 |
Incorrect |
448 ms |
15876 KB |
Output isn't correct |
14 |
Execution timed out |
521 ms |
19308 KB |
Time limit exceeded |
15 |
Execution timed out |
601 ms |
17580 KB |
Time limit exceeded |
16 |
Execution timed out |
646 ms |
18628 KB |
Time limit exceeded |
17 |
Execution timed out |
666 ms |
21180 KB |
Time limit exceeded |
18 |
Execution timed out |
659 ms |
15388 KB |
Time limit exceeded |
19 |
Execution timed out |
720 ms |
22424 KB |
Time limit exceeded |
20 |
Execution timed out |
786 ms |
23120 KB |
Time limit exceeded |