제출 #653953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653953		guagua0407	사다리꼴 (balkan11_trapezoid)	C++17	14 / 100	354 ms	53376 KiB

trapezoid

/*
希望能進全國賽
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
	ll a,b,c,d;
};

const ll mxn=2e5+5;
node num[mxn];
vector<pair<ll,ll>> as[mxn],bs[mxn];
pair<ll,ll> ans[mxn];
pair<ll,ll> segtree[mxn*4];
map<ll,ll> idup,iddown;
ll cntup=0;
ll cntdown=0;

pii comb(pii a,pii b){
	if(a.f==b.f){
		return {a.f,a.s+b.s};
	}
	return max(a,b);
}

void update(ll pos,pii val,ll l=1,ll r=cntdown,ll v=1){
	if(l==r){
		segtree[v]=comb(segtree[v],val);
		return;
	}
	ll mid=(l+r)/2;
	if(pos<=mid) update(pos,val,l,mid,v*2);
	else update(pos,val,mid+1,r,v*2+1);
	segtree[v]=comb(segtree[v*2],segtree[v*2+1]);
}

pair<ll,ll> query(ll tl,ll tr,ll l=1,ll r=cntdown,ll v=1){
	if(tl>tr){
		return {0,0};
	}
	if(tl<=l and r<=tr){
		return segtree[v];
	}
	ll mid=(l+r)/2;
	return comb(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}

int main() {_
	//setIO("wayne");
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++){
		ll a,b,c,d;
		cin>>a>>b>>c>>d;
		num[i]={a,b,c,d};
		idup[a]++;
		idup[b]++;
		iddown[c]++;
		iddown[d]++;
	}
	for(auto &v:idup){
		cntup++;
		v.s=cntup;
	}
	for(auto &v:iddown){
		cntdown++;
		v.s=cntdown;
	}
	for(ll i=1;i<=n;i++){
		as[idup[num[i].a]].push_back({iddown[num[i].c],i});
		bs[idup[num[i].b]].push_back({iddown[num[i].d],i});
	}
	for(ll i=1;i<=cntup;i++){
		for(auto v:as[i]){
			//cout<<"a "<<v.s<<'\n';
			pii tmp=query(1,v.f-1);
			ans[v.s]={tmp.f+1,tmp.s+(tmp.f==0)};
		}
		for(auto v:bs[i]){
			//cout<<"b "<<v.s<<'\n';
			update(v.f,ans[v.s]);
		}
		//cout<<'\n';
	}
	cout<<segtree[1].f<<' '<<segtree[1].s<<'\n';
	return 0;
}
//maybe its multiset not set

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

trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 100