제출 #122133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122133		hamzqq9	사다리꼴 (balkan11_trapezoid)	C++14	100 / 100	155 ms	6520 KiB

trapezoid

#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);

}

컴파일 시 표준 에러 (stderr) 메시지

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);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100