oj.uz

답안 #653956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653956 2022-10-29T04:25:00 Z guagua0407 사다리꼴 (balkan11_trapezoid) C++17
0 / 100
 342 ms 41172 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<pii> as[mxn],bs[mxn];
pii ans[mxn];
pii 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]);
}

pii 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+1<<' '<<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
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Incorrect 6 ms 9684 KB Output isn't correct
3 Incorrect 7 ms 9812 KB Output isn't correct
4 Incorrect 7 ms 9960 KB Output isn't correct
5 Incorrect 10 ms 10272 KB Output isn't correct
6 Incorrect 11 ms 10580 KB Output isn't correct
7 Incorrect 13 ms 10892 KB Output isn't correct
8 Incorrect 17 ms 11348 KB Output isn't correct
9 Incorrect 37 ms 12888 KB Output isn't correct
10 Incorrect 53 ms 16156 KB Output isn't correct
11 Incorrect 76 ms 17460 KB Output isn't correct
12 Incorrect 172 ms 25452 KB Output isn't correct
13 Incorrect 216 ms 28156 KB Output isn't correct
14 Incorrect 230 ms 32816 KB Output isn't correct
15 Incorrect 255 ms 34368 KB Output isn't correct
16 Incorrect 308 ms 35580 KB Output isn't correct
17 Incorrect 301 ms 36996 KB Output isn't correct
18 Incorrect 255 ms 38388 KB Output isn't correct
19 Incorrect 293 ms 39168 KB Output isn't correct
20 Incorrect 342 ms 41172 KB Output isn't correct