#1012873 (C++23(gcc13)) No.2974 関数の芽

提出ソース

結果

問題	No.2974 関数の芽
ユーザー	👑 binap
提出日時	2024-09-22 17:56:31
言語	C++23(gcc13) (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	562 ms / 2,000 ms
コード長	5,185 bytes
コンパイル時間	8,361 ms
コンパイル使用メモリ	337,884 KB
実行使用メモリ	28,552 KB
最終ジャッジ日時	2024-09-22 19:30:22
合計ジャッジ時間	14,870 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	5 ms 6,944 KB
testcase_13	AC	33 ms 6,944 KB
testcase_14	AC	269 ms 16,120 KB
testcase_15	AC	397 ms 20,448 KB
testcase_16	AC	491 ms 27,608 KB
testcase_17	AC	536 ms 27,040 KB
testcase_18	AC	558 ms 28,488 KB
testcase_19	AC	562 ms 28,056 KB
testcase_20	AC	544 ms 27,916 KB
testcase_21	AC	556 ms 27,952 KB
testcase_22	AC	539 ms 28,088 KB
testcase_23	AC	535 ms 28,552 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;

template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}

template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}

struct Query{
	long long k, l, m, n, x;
};

struct Rational{
	long long up, down;
	Rational(long long _up, long long _down){
		assert(_down != 0);
		int c = 1;
		if(_up < 0){c *= -1; _up *= -1;}
		if(_down < 0){c *= -1; _down *= -1;}
		long long g = gcd(_up, _down);
		up = c * _up / g;
		down = _down / g;
	}
	bool operator<(const Rational& right) const{
		return up * right.down < right.up * down;
	}
	bool operator==(const Rational& right) const{
		return (up * right.down - right.up * down) == 0;
	}
};

// Coodinate Compression
// https://youtu.be/fR3W5IcBGLQ?t=8550
template<typename T=int>
struct CC {
  bool initialized;
  vector<T> xs;
  CC(): initialized(false) {}
  void add(T x) { xs.push_back(x);}
  void init() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    initialized = true;
  }
  int operator()(T x) {
    if (!initialized) init();
    return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
  }
  T operator[](int i) {
    if (!initialized) init();
    return xs[i];
  }
  int size() {
    if (!initialized) init();
    return xs.size();
  }
};

using S = pair<long long, long long>;
S op(S a, S b){
	return make_pair(a.first + b.first, a.second + b.second);
}
S e(){
	return make_pair(0LL, 0LL);
}
using F = pair<long long, long long>;
S mapping(F f, S x){
	return make_pair(f.first + x.first, f.second + x.second);
}
F composition(F f, F g){
	return make_pair(f.first + g.first, f.second + g.second);
}
F id(){
	return make_pair(0LL, 0LL);
}

const long long INF = 1001001001;

int main(){
	int q;
	cin >> q;
	vector<Query> querys;
	CC<Rational> cc;
	cc.add(Rational{-INF, 1});
	cc.add(Rational{INF, 1});
	rep(i, q){
		long long k, l, m, n, x;
		cin >> k >> l >> m >> n >> x;
		querys.emplace_back(k, l, m, n, x);
		if(k != 0) cc.add(Rational{-l, k});
		if(m != 0) cc.add(Rational{-n, m});
		cc.add(Rational{x, 1});
	}
	int sz = cc.size();
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(sz);
	
	/*
	for(auto rational : cc.xs){
		cout << rational.up << ' ' << rational.down << "\n";
	}
	*/
	
	// apply F(x) += c * max(kx + l, 0)
	auto add = [&](long long k, long long l, long long c){
		if(k > 0){
			seg.apply(cc(Rational(-l, k)), sz, make_pair(c * k, c * l));
		}
		if(k == 0){
			if(l > 0) seg.apply(0, sz, make_pair(0, c * l));
		}
		if(k < 0){
			seg.apply(0, cc(Rational(-l, k)), make_pair(c * k, c * l));
		}
	};
	auto judge = [&](long long x){
		int idx = cc(Rational{x, 1});
		auto line_left = seg.get(idx - 1);
		auto line_right = seg.get(idx);
//		cout << line_left << "\n";
//		cout << line_right << "\n";
		if(line_left != e()) return false;
		if(line_right != e()) return false;
		return true;
	};
	rep(i, q){
		auto [k, l, m, n, x] = querys[i];
		add(k, l, 1);
		add(m, n, -1);
		if(judge(x)) cout << "Yes\n";
		else cout << "No\n";
		/*
		rep(idx, sz) cout << seg.get(idx) << ' ';
		cout << "\n";
		*/
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード