#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[20];
map<int, int> mp;
struct make{
int v = 0, cnt = 1;
} tre[20], ans[20];
make operator + (make a, make b) {
make c;
c.cnt = 0;
c.v = a.v;
if(b.v>a.v)
c.v = b.v;
if(a.v==c.v)
c.cnt+=a.cnt;
if(b.v==c.v)
c.cnt+=b.cnt;
c.cnt%=30013;
return c;
}
void upd(make x, int p) {
while(p<=19)
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<=19)
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() {
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:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
1 ms |
212 KB |
Partially correct |
2 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
6 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
7 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
10 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
11 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
12 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
13 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
14 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
15 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
16 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
17 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
18 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
19 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
20 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |