Submission #653954

#	Time	Username	Problem	Language	Result	Execution time	Memory
653954		guagua0407	trapezoid (balkan11_trapezoid)	C++17	46 / 100	326 ms	41024 KiB

trapezoid

/*
希望能進全國賽
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#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{
	int a,b,c,d;
};

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

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

void update(int pos,pii val,int l=1,int r=cntdown,int v=1){
	if(l==r){
		segtree[v]=comb(segtree[v],val);
		return;
	}
	int 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<int,int> query(int tl,int tr,int l=1,int r=cntdown,int v=1){
	if(tl>tr){
		return {0,0};
	}
	if(tl<=l and r<=tr){
		return segtree[v];
	}
	int 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");
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int 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(int 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(int 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

Compilation message (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: 46 / 100