답안 #122133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122133 2019-06-27T16:20:17 Z hamzqq9 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
155 ms 6520 KB
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 30013 
#define N 100005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

struct trap {

	int a,b,c,d;
	int pos;

} t[N];

int n;
int mx[N],wa[N],b[N],d[N];
int ptr[N/KOK+5],ans[N/KOK+5],cnt[N/KOK+5],dd[N/KOK+5];

int add(int a,int b) {

	a+=b;

	if(a>=MOD) a-=MOD;

	return a;

}
	
void upd(ii& a,ii b) {

	if(b.st>a.st) {

		a=b;

	}
	else if(b.st==a.st) {

		a.nd=add(a.nd,b.nd);
	
	}

}

void up(int pos) {

	int bl=(pos-1)/KOK;

	if(ptr[bl]>=pos) {

		ii now={ans[bl],cnt[bl]};

		upd(now,{mx[pos],wa[pos]});

		ans[bl]=now.st;
		cnt[bl]=now.nd;

	}

}

ii get(int ind) {

	int cur=0;

	ii res={0,1};

	for(int i=1;i<=n;i+=KOK,cur++) {

		while(ptr[cur]+1<min(i+KOK,n+1) && b[ptr[cur]+1]<t[ind].a) {

			++ptr[cur];

			up(ptr[cur]);

		}

		if(dd[cur]>t[ind].c) {

			for(int j=i;j<=ptr[cur];j++) {

				if(d[j]<t[ind].c) {	

					upd(res,{mx[j],wa[j]});

				}

			}

			break ;

		}
		else {

			upd(res,{ans[cur],cnt[cur]});

		}

	}

	res.st++;

	return res;

}

void pre() {

	sort(t+1,t+1+n,[](trap x,trap y) {

		return x.d<y.d;

	});

	int cur=0;

	for(int i=1;i<=n;i+=KOK,cur++) {

		int sz=min(KOK,n-i+1);

		sort(t+i,t+i+sz,[](trap x,trap y) {

			return x.b<y.b;

		});

		for(int j=i;j<i+sz;j++) {
		
			b[j]=t[j].b;
			d[j]=t[j].d;

			umax(dd[cur],d[j]);

		}

		ans[cur]=-1;
		ptr[cur]=i-1;

	}

	for(int i=1;i<=n;i++) t[i].pos=i;

}

int main() {
	
	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d %d %d %d",&t[i].a,&t[i].b,&t[i].c,&t[i].d);
	
	pre();

	sort(t+1,t+1+n,[](trap x,trap y){

		return x.a<y.a;

	});

	for(int i=1;i<=n;i++) {

		ii res=get(i); // index
		
		mx[t[i].pos]=res.st;
		wa[t[i].pos]=res.nd;

//		cerr<<i<<" "<<mx[t[i].pos]<<'\n';

		up(t[i].pos);

	}

	int m=0,c=0;

	for(int i=1;i<=n;i++) {

		if(mx[i]>m) {

			m=mx[i];
			c=wa[i];

		}
		else if(mx[i]==m) c=add(c,wa[i]);

	}

	printf("%d %d",m,c);

}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
trapezoid.cpp:166:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d %d %d %d",&t[i].a,&t[i].b,&t[i].c,&t[i].d);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 13 ms 896 KB Output is correct
10 Correct 19 ms 1656 KB Output is correct
11 Correct 24 ms 1892 KB Output is correct
12 Correct 80 ms 3516 KB Output is correct
13 Correct 85 ms 4088 KB Output is correct
14 Correct 92 ms 4856 KB Output is correct
15 Correct 107 ms 5052 KB Output is correct
16 Correct 117 ms 5368 KB Output is correct
17 Correct 146 ms 5724 KB Output is correct
18 Correct 108 ms 6028 KB Output is correct
19 Correct 119 ms 6264 KB Output is correct
20 Correct 155 ms 6520 KB Output is correct