제출 #1267285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267285		_rain_	trapezoid (balkan11_trapezoid)	C++20	100 / 100	89 ms	16200 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";

template<class T1 , class T2>	
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 1e5;
const int MOD = 30013;
	int add(int a , int b){
		return a + b >= MOD ? a + b - MOD : a + b;
	}
	
	struct Node{
		int a , b , c , d;
		void read(){
			cin >> a >> b >> c >> d;
			return;
		}
	};
	Node pol[N + 2];
	
	int n;
	
namespace subtask2{
	bool check(){
		return true;
	}
	
	int id[2][N + 2] = {} , lef[2][N + 2] = {} , rig[2][N + 2] = {};
	
	int dp[N + 2] = {} , cnt[N + 2] = {};
		
		pair<int,int> st[N * 4 + 2] ;
		
		pair<int,int> pushup(pair<int,int> a , pair<int,int> b){
			if (a.first > b.first) return a;
			if (a.first < b.first) return b;
			return {a.first , add(a.second , b.second)};
		}
		
			void update(int id , int l , int r , int p , pair<int,int> val){
				if (l == r) st[id] = val;
				else{
					int m = (l + r) / 2;
					if (p <= m) update(id * 2 , l , m , p , val);
						else update(id * 2 + 1 , m + 1 , r , p , val);
					st[id] = pushup(st[id * 2] , st[id * 2 + 1]);
				}
				return;
			}
			pair<int,int> Get(int id , int l , int r , int u , int v){
				if (l > v || r < u) return {0 , 1};
				if (u <= l && r <= v) return st[id];
				int m = (l + r) / 2;
				return pushup(Get(id * 2 , l , m , u , v) , Get(id * 2 + 1 , m + 1 , r , u , v));
			}
		
		vector<int> ask[N + 2] , add_queri[N + 2];
	
	void main_code(){
		for(int i = 1; i <= n; ++i) {
			id[0][i] = i;
			id[1][i] = i;
		}
		
			sort(id[0] + 1 , id[0] + n + 1 , [&](int i , int j){
				return pol[i].b < pol[j].b;	
			});
			sort(id[1] + 1 , id[1] + n + 1 , [&](int i , int j){
				return pol[i].a < pol[j].a;	
			});
		
		for(int i = 1; i <= n; ++i) lef[0][id[0][i]] = i;
		for(int i = 1 , j = 1; i <= n; ++i){
			while (j <= n && pol[id[0][j]].b < pol[id[1][i]].a) ++j;
			lef[1][id[1][i]] = j - 1;
		}
		
			sort(id[0] + 1 , id[0] + n + 1 , [&](int i , int j){
				return pol[i].d < pol[j].d;	
			});
			sort(id[1] + 1 , id[1] + n + 1 , [&](int i , int j){
				return pol[i].c < pol[j].c;	
			});
		
		for(int i = 1; i <= n; ++i) rig[0][id[0][i]] = i;
		for(int i = 1 , j = 1; i <= n; ++i){
			while (j <= n && pol[id[0][j]].d < pol[id[1][i]].c) ++j;
			rig[1][id[1][i]] = j - 1;
		}
		
		for(int i = 1; i <= n; ++i){
			ask[lef[1][i]].push_back(i);
			add_queri[lef[0][i]].push_back(i);
		}
		
		for(int i = 1; i <= n; ++i) {
			dp[i] = cnt[i] = 1;
		}
				
		for(int i = 0 ; i <= n; ++i){
			for(auto& x : add_queri[i]){
//				if (dp[x] == 0) cout << "DUMA : " << i << ' ' << x << '\n';
				update(1 , 1 , n , rig[0][x] , {dp[x] + 1, cnt[x]});
			}
			
			for(auto& x : ask[i]) {
				pair<int,int> kq = Get(1 , 1 , n , 1 , rig[1][x]);
				if (kq.first < dp[x]) continue;
				dp[x] = kq.first;
				cnt[x] = kq.second;
			}
		}

		int mx = 0 , res_cnt = 0;
		for(int i = 1; i <= n; ++i){
			if (maximize(mx , dp[i])) res_cnt = cnt[i]; 
				else if (mx == dp[i]) res_cnt = add(res_cnt , cnt[i]);
		}
//		for(int i = 1; i <= n; ++i) cout << cnt[i] << '\n';
		cout << mx << ' ' << res_cnt << '\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0)  ; cout.tie(0); 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n;
		for(int i = 1; i <= n; ++i) pol[i].read();
		
		
		return subtask2::main_code() , 0;
	return 0;
}

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

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:152:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:153:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100