제출 #1344883

#제출 시각아이디문제언어결과실행 시간메모리
1344883cnam9Boat (APIO16_boat)C++20
100 / 100
584 ms1796 KiB
#include<bits/stdc++.h>
#define V for
using namespace std;using _=decltype(0);using __=decltype(67ll);constexpr _ e=500;constexpr _ l=1e9+7;_ n;pair<_,_>y[e];_ p[e*2];_ i[e+1];_ u(_ y,_ f){V(_ k=l-2;k;k>>=1){if (k&1)y=(__)y*f%l;f=(__)f*f%l;}return y;}struct{vector<_>k;_ q(_ f){_ g=0;_ xi=1;V(_ r=0;r<k.size();r++){xi=(__)xi*(f-r)%l;g=(g+(__)k[r]*xi%l*i[r+1])%l;}return g;}void j(_ c){k.push_back(0);V(_ r=k.size()-1;r;r--){k[r]=(k[r]+(__)k[r-1]*i[r])%l;}k[0]=(k[0]+c)%l;}} a[2*e];_ main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);_ n;cin>>n;V(_ f=1;f<=n;f++){i[f]=u(1,f);}V(_ r=0;r<n;r++){auto&[z,o]=y[r];cin>>z>>o;o++;p[r*2]=z;p[r*2+1]=o;}sort(p,p+2*n);_ x=unique(p,p+2*n)-p-1;V(_ r=0;r<n;r++){auto[z,o]=y[r];__ g=1;_ h=0;V(;p[h]<z;h++){g+=a[h].q(p[h+1])-a[h].q(p[h])+l;}g%=l;V(;p[h]<o;h++){_ c=(g-a[h].q(p[h])+l)%l;_ j=(c+a[h].q(p[h+1]))%l;a[h].j(c);g=j;}}__ g=0;V(_ h=0;h<x;h++){g+=a[h].q(p[h+1])-a[h].q(p[h]);}cout<<(g%l+l)%l;return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...