oj.uz

Submission #653952

# Submission time Handle Problem Language Result Execution time Memory
653952 2022-10-29T04:16:55 Z guagua0407 trapezoid (balkan11_trapezoid) C++17
46 / 100
 358 ms 40896 KB 
/*
希望能進全國賽
*/
#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){
		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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9744 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Partially correct 6 ms 9812 KB Partially correct
4 Partially correct 9 ms 9940 KB Partially correct
5 Partially correct 10 ms 10324 KB Partially correct
6 Partially correct 11 ms 10580 KB Partially correct
7 Partially correct 15 ms 10964 KB Partially correct
8 Partially correct 21 ms 11348 KB Partially correct
9 Partially correct 34 ms 12984 KB Partially correct
10 Partially correct 46 ms 16164 KB Partially correct
11 Partially correct 70 ms 17620 KB Partially correct
12 Partially correct 151 ms 25464 KB Partially correct
13 Partially correct 189 ms 28204 KB Partially correct
14 Partially correct 222 ms 32972 KB Partially correct
15 Partially correct 274 ms 34372 KB Partially correct
16 Partially correct 297 ms 35672 KB Partially correct
17 Partially correct 289 ms 37036 KB Partially correct
18 Partially correct 240 ms 38392 KB Partially correct
19 Partially correct 287 ms 39228 KB Partially correct
20 Partially correct 358 ms 40896 KB Partially correct