Submission #12036

#TimeUsernameProblemLanguageResultExecution timeMemory
12036gs14004trapezoid (balkan11_trapezoid)C++98
45 / 100
239 ms15476 KiB
#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; int n; int a[100005], b[100005], c[100005], d[100005]; int dp[100005]; int num[100005], cnt[100005], pcnt[100005]; int rcnt[100005]; struct seg{int a,b,p,i;}st[100005]; bool cmp(seg a, seg b){return a.a < b.a;} struct seg2{int dp,a,b,p,i,num;}st2[100005]; bool cmp2(seg2 a, seg2 b){return a.b < b.b;} bool cmp3(seg2 a, seg2 b){return a.a < b.a;} struct rmq{ int lim, tree[530000]; void init(int n){ for(lim = 1; lim <= n; lim <<= 1); } void ins(int s, int v){ s += lim; tree[s] = v; while(s>1){ s >>= 1; tree[s] = max(tree[2*s],tree[2*s+1]); } } int q(int s, int e){ s += lim; e += lim; int r = 0; while(s<e){ if(s%2 == 1) r = max(r,tree[s++]); if(e%2 == 0) r = max(r,tree[e--]); s >>= 1; e >>= 1; } if(s == e) r = max(r,tree[s]); return r; } }rmq; struct idx{ int lim, tree[530000]; void init(int n){ for(lim = 1; lim <= n; lim <<= 1); } void ins(int s, int v){ s += lim; tree[s] = v; while(s>1){ s >>= 1; tree[s] = tree[2*s] + tree[2*s+1]; tree[s] %= 30013; } } int q(int s, int e){ s += lim; e += lim; int r = 0; while(s<e){ if(s%2 == 1) r += tree[s++]; if(e%2 == 0) r += tree[e--]; s >>= 1; e >>= 1; } if(s == e) r += tree[s]; return r % 30013; } }idx; void input(){ vector<int> vu, vd; scanf("%d",&n); rmq.init(2*n); for (int i=0; i<n; i++) { scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]); vu.push_back(a[i]); vu.push_back(b[i]); vd.push_back(c[i]); vd.push_back(d[i]); } sort(vu.begin(),vu.end()); sort(vd.begin(),vd.end()); for (int i=0; i<n; i++) { a[i] = (int)(lower_bound(vu.begin(),vu.end(),a[i]) - vu.begin()); b[i] = (int)(lower_bound(vu.begin(),vu.end(),b[i]) - vu.begin()); c[i] = (int)(lower_bound(vd.begin(),vd.end(),c[i]) - vd.begin()); d[i] = (int)(lower_bound(vd.begin(),vd.end(),d[i]) - vd.begin()); st[2*i] = {a[i],c[i],0,i}; st[2*i+1] = {b[i],d[i],1,i}; } sort(st,st+2*n,cmp); } int main(){ input(); for (int i=0; i<2*n; i++) { if(st[i].p == 0){ dp[st[i].i] = rmq.q(0,st[i].b) + 1; st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1}; } else{ rmq.ins(st[i].b,dp[st[i].i]); st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1}; } } int mcnt = *max_element(dp,dp+n); printf("%d ",mcnt); for (int i=0; i<n; i++) { cnt[dp[i]]++; } for (int i=1; i<=n; i++) { cnt[i] += cnt[i-1]; } sort(st2,st2+2*n,cmp2); for (int i=0; i<2*n; i++) { if(st2[i].p == 0){ num[st2[i].i] = st2[i].num = cnt[dp[st2[i].i] - 1] + (pcnt[dp[st2[i].i]]++); } else{ st2[i].num = num[st2[i].i]; } } sort(st2,st2+2*n,cmp3); idx.init(n); for (int i=0; i<2*n; i++) { if(st2[i].p == 0){ if(st2[i].dp == 1) rcnt[st2[i].i] = 1; else rcnt[st2[i].i] = idx.q(cnt[st2[i].dp-2], cnt[st2[i].dp-1]-1); } else{ idx.ins(st2[i].num,rcnt[st2[i].i]); } } int acnt = 0; for (int i=0; i<n; i++) { if(dp[i] == mcnt){ acnt += rcnt[i]; acnt %= 30013; } } printf("%d",acnt); }

Compilation message (stderr)

trapezoid.cpp: In function 'void input()':
trapezoid.cpp:94:33: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i] = {a[i],c[i],0,i};
                                 ^
trapezoid.cpp:94:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i] = {a[i],c[i],0,i};
                 ^
trapezoid.cpp:95:35: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i+1] = {b[i],d[i],1,i};
                                   ^
trapezoid.cpp:95:19: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i+1] = {b[i],d[i],1,i};
                   ^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:105:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
                                                               ^
trapezoid.cpp:105:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
                    ^
trapezoid.cpp:109:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
                                                               ^
trapezoid.cpp:109:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
                    ^
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:78:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:81:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
                                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...