# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
825569 | boyliguanhan | 사다리꼴 (balkan11_trapezoid) | C++17 | 194 ms | 11040 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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:a<c.a;
}
} traps[200100];
struct make{
int v = 0, cnt = 0;
make operator + (make b) {
make c;
c.v = max(v, b.v);
if(v==c.v)
c.cnt=cnt;
if(b.v==c.v)
c.cnt+=b.cnt;
c.cnt%=30013;
return c;
}
} tre[200100], ans[200100];
void upd(make x, int p) {
while(p<=2e5)
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<=2e5)
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({traps[i].b, traps[i].d, i});
for(int j = mid+1; j <= r; j++)
tp.push_back({traps[j].a, traps[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(traps[i].d);
tp.clear();
cdq(mid+1, r);
}
int main() {
ans[0].cnt = 1;
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> traps[i].a >> traps[i].b >> traps[i].c >> traps[i].d;
sort(traps, traps+n);
cdq(0,n-1);
for(int i = 0; i < n; i++)
ans[n]=ans[n]+ans[i];
cout << ans[n].v << ' ' << ans[n].cnt << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |