제출 #198817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198817		mahmoudbadawy	사다리꼴 (balkan11_trapezoid)	C++17	40 / 100	157 ms	5992 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5,MOD=30013;

struct trap{
	int l1,r1,l2,r2;
} arr[N];

vector<int> cmp;
int btree[2*N*4],dp[N];
int sortl[N],sortr[N];
int n;

bool cmp1(int a,int b)
{
	return arr[a].l1<arr[b].l1;
}

bool cmp2(int a,int b)
{
	return arr[a].r1<arr[b].r1;
}

int get(int x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin()+1;
}

inline int add(int x,int y)
{
	int res=x+y;
	if(res<0) res+=MOD;
	if(res>=MOD) res-=MOD;
	return res;
}

void update(int node,int l,int r,int ind,int val)
{
	if(l==r)
	{
		btree[node]=val;
		return;
	}
	int mid=(l+r)/2;
	if(ind<=mid)
		update(node*2,l,mid,ind,val);
	else
		update(node*2+1,mid+1,r,ind,val);
	btree[node]=max(btree[node*2],btree[node*2+1]);
}


int query(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)/2;
	return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&arr[i].l1,&arr[i].r1,&arr[i].l2,&arr[i].r2);
		cmp.push_back(arr[i].l2); cmp.push_back(arr[i].r2);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	for(int i=0;i<n;i++)
	{
		arr[i].l2=get(arr[i].l2); arr[i].r2=get(arr[i].r2);
	}
	int m=cmp.size();
	iota(sortl,sortl+n,0); iota(sortr,sortr+n,0);
	sort(sortl,sortl+n,cmp1); sort(sortr,sortr+n,cmp2);
	int y=0;
	for(int i=0;i<n;i++)
	{
		int x=sortl[i];
		while(y<n&&arr[sortr[y]].r1<arr[x].l1)
		{
			//cout << "GOT: " << arr[sortr[y]].l1 << " " << arr[sortr[y]].r1 << " " << arr[sortr[y]].r2 << endl;
			update(1,0,m,arr[sortr[y]].r2,dp[sortr[y]]);
			y++;
		}
		dp[x]=1+query(1,0,m,0,arr[x].l2);
		/*cout << dp[x] << endl;
		cout << arr[x].l1 << " " << arr[x].r1 << " " << arr[x].l2 << " " << arr[x].r2 << endl;*/
	}
	int maxi=0;
	for(int i=0;i<n;i++)
		maxi=max(maxi,dp[i]);
	cout << maxi << " 0" << endl;
}

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

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
trapezoid.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&arr[i].l1,&arr[i].r1,&arr[i].l2,&arr[i].r2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100