oj.uz

답안 #74720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74720 2018-09-07T00:37:38 Z OmarHashim 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 190 ms 33012 KB 
#include<bits/stdc++.h>
using namespace std;

#define scl(x) scanf("%lld",&x)
#define sc(x)  scanf("%d",&x)
#define ll long long
#define lop(i,n) for(int i=0;i<n;++i)
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const int mod=30013;
int add(int a,int b){
	a+=b;
	if(a>=mod)a-=mod;
	return a;
}

const int N=1e5+100,LG=24;
ii tree[N*LG];
int L[N*LG],R[N*LG],ne;
ii dp[N];
void build(int root,int s,int e){
	if(s==e)return;
	L[root]=ne++;
	R[root]=ne++;
	int m=s+((e-s)>>1);
	build(L[root],s,m);
	build(R[root],m+1,e);
}
ii merge(ii a,ii b){
	if(a.first>b.first)return a;
	if(b.first>a.first)return b;
	return ii(a.first,add(a.second,b.second));

}
void upd(int nroot,int root,int s,int e,int i,ii val){
	if(s==e){
		tree[nroot]=merge(tree[root],val);
		return;
	}
	int m=s+((e-s)>>1);
	if(i<=m){
		L[nroot]=ne++;
		R[nroot]=R[root];
		upd(L[nroot],L[root],s,m,i,val);
	}
	else {
		L[nroot]=L[root];
		R[nroot]=ne++;
		upd(R[nroot],R[root],m+1,e,i,val);
	}
	tree[nroot]=merge(tree[L[nroot]],tree[R[nroot]]);
}
ii get(int root,int s,int e,int l,int r){
	if(e<l||s>r)return ii(0,0);
	if(s>=l&&e<=r)return tree[root];
	int m=s+((e-s)>>1);
	return merge(get(L[root],s,m,l,r),get(R[root],m+1,e,l,r));
}


struct node{
	int a,b,c,d;
	bool operator<(const node &o)const{
		return a<o.a;
	}
}arr[N];
int n;
vector<int> uncom;
int roots[N];

int main(){
#ifndef ONLINE_JUDGE
	//freopen("i.txt","r",stdin);
#endif
	sc(n);
	lop(i,n){
		sc(arr[i].a),sc(arr[i].b);
		sc(arr[i].c),sc(arr[i].d);
		uncom.push_back(arr[i].c);
	}
	uncom.push_back(1e9+1);
	sort(uncom.begin(),uncom.end());
	uncom.erase(unique(uncom.begin(),uncom.end()),uncom.end());
	lop(i,n){
		arr[i].c=lower_bound(uncom.begin(),uncom.end(),arr[i].c)-uncom.begin();
		arr[i].d=upper_bound(uncom.begin(),uncom.end(),arr[i].d)-uncom.begin();
	}
	sort(arr,arr+n);
	roots[n+1]=ne++;
	build(roots[n+1],0,uncom.size()-1);
	arr[n].a=1e9+1;
	upd(roots[n],roots[n+1],0,uncom.size()-1,uncom.size()-1,ii(0,1));
	for(int i=n-1;i>=0;i--){
		node qr;
		qr.a=arr[i].b;
		int start=upper_bound(arr+i+1,arr+n+1,qr)-arr;
		dp[i]=get(roots[start],0,uncom.size()-1,arr[i].d,uncom.size()-1);
		if(!dp[i].first)dp[i].second=1;
		dp[i].first++;
		roots[i]=ne++;
		upd(roots[i],roots[i+1],0,uncom.size()-1,arr[i].c,dp[i]);
	}
	ii out(0,0);
	lop(i,n)
		out=merge(out,dp[i]);
	printf("%d %d\n",out.first,out.second);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sc(x)  scanf("%d",&x)
                ~~~~~^~~~~~~~~
trapezoid.cpp:76:2: note: in expansion of macro 'sc'
  sc(n);
  ^~
trapezoid.cpp:78:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sc(arr[i].a),sc(arr[i].b);
               ^
trapezoid.cpp:78:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
trapezoid.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sc(arr[i].c),sc(arr[i].d);
               ^
trapezoid.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 4 ms 928 KB Output is correct
6 Correct 6 ms 1224 KB Output is correct
7 Correct 7 ms 1480 KB Output is correct
8 Correct 10 ms 1784 KB Output is correct
9 Correct 17 ms 3192 KB Output is correct
10 Correct 33 ms 6392 KB Output is correct
11 Correct 40 ms 7928 KB Output is correct
12 Correct 89 ms 16000 KB Output is correct
13 Correct 113 ms 19504 KB Output is correct
14 Correct 127 ms 22800 KB Output is correct
15 Correct 154 ms 24504 KB Output is correct
16 Correct 174 ms 26172 KB Output is correct
17 Correct 180 ms 27964 KB Output is correct
18 Correct 149 ms 29620 KB Output is correct
19 Correct 157 ms 31288 KB Output is correct
20 Correct 190 ms 33012 KB Output is correct