Submission #5219

#TimeUsernameProblemLanguageResultExecution timeMemory
5219woqja125trapezoid (balkan11_trapezoid)C++98
100 / 100
113 ms12056 KiB
#include<stdio.h> #include<algorithm> struct data { int a, b, n, t; } dat[200001]; struct coor { int *p; } Y[200001]; struct node { int max; int cnt; } IT[700001]; bool operator<(const coor &A, const coor &B) { return *A.p<*B.p; } bool operator<(const data &A, const data &B) { return A.a<B.a; } int d[100001][2]; node getmax(int f, int r) { node re={ 0, 0 }; while(f<r) { if(f%2 == 1) { if(re.max == IT[f].max) (re.cnt += IT[f].cnt)%=30013; else if(re.max < IT[f].max) re = IT[f]; f++; } if(r%2 == 0) { if(re.max == IT[r].max) (re.cnt += IT[r].cnt)%=30013; else if(re.max < IT[r].max) re = IT[r]; r--; } f/=2; r/=2; } if(f==r) { if(re.max == IT[r].max) (re.cnt += IT[r].cnt)%=30013; else if(re.max < IT[r].max) re = IT[r]; } return re; } void init(int x) { while(x/=2) { if(IT[x*2].max == IT[x*2+1].max) { IT[x].max = IT[x*2].max; IT[x].cnt = (IT[x*2].cnt + IT[x*2+1].cnt)%30013; } else if(IT[x*2].max < IT[x*2+1].max) { IT[x] = IT[x*2+1]; } else { IT[x] = IT[x*2]; } } } int main() { int n, i, a, b, c, D, base; node t; scanf("%d", &n); for(base = 1; base<2*n; base*=2); for (i = 1; i <= n; i++) { scanf("%d%d%d%d", &a, &b, &c, &D); dat[i*2-1].a = a; dat[i*2].a = b; dat[i*2-1].b = c; dat[i*2].b = D; dat[i*2-1].t = 0; dat[i*2].t = 1; dat[i*2-1].n = dat[i*2].n = i; Y[2*i-1].p = &dat[i*2-1].b; Y[2*i].p = &dat[i*2].b; } std::sort(Y+1, Y+1+2*n); for(i=1; i<=2*n; i++) *Y[i].p = i; std::sort(dat+1, dat+1+2*n); IT[base].cnt = 1; init(base); for(i=1; i<=2*n; i++) { if(dat[i].t==0) { t = getmax(base, base+dat[i].b); d[dat[i].n][0] = t.max + 1; d[dat[i].n][1] = t.cnt; } else { IT[base + dat[i].b].max = d[dat[i].n][0]; IT[base + dat[i].b].cnt = d[dat[i].n][1]; init(base+dat[i].b); } } t = getmax(base, base+2*n); printf("%d %d", t.max, t.cnt); return 0; }

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:75:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
trapezoid.cpp:79:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &D);
                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...