#896027 (C++17) No.2395 区間二次変換一点取得

提出ソース

結果

問題	No.2395 区間二次変換一点取得
ユーザー	YocyCraft
提出日時	2023-07-28 21:40:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	133 ms / 2,000 ms
コード長	6,300 bytes
コンパイル時間	2,469 ms
コンパイル使用メモリ	213,248 KB
実行使用メモリ	8,032 KB
最終ジャッジ日時	2024-10-06 18:03:48
合計ジャッジ時間	5,199 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 6,816 KB
testcase_01	AC	7 ms 6,816 KB
testcase_02	AC	7 ms 6,820 KB
testcase_03	AC	6 ms 6,816 KB
testcase_04	AC	7 ms 6,816 KB
testcase_05	AC	7 ms 6,816 KB
testcase_06	AC	7 ms 6,816 KB
testcase_07	AC	7 ms 6,820 KB
testcase_08	AC	7 ms 6,816 KB
testcase_09	AC	7 ms 6,816 KB
testcase_10	AC	7 ms 6,816 KB
testcase_11	AC	7 ms 6,820 KB
testcase_12	AC	17 ms 6,816 KB
testcase_13	AC	129 ms 7,936 KB
testcase_14	AC	130 ms 7,936 KB
testcase_15	AC	130 ms 7,936 KB
testcase_16	AC	129 ms 7,936 KB
testcase_17	AC	133 ms 7,936 KB
testcase_18	AC	93 ms 8,032 KB
testcase_19	AC	95 ms 7,936 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;

#define tp3(T) tuple<T,T,T>
#define tp4(T) tuple<T,T,T,T>

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-(a).begin())
#define outrange(x,min,max) ((x)<(min) || (x)>(max))

ll _start_time;
#define nano (chrono::system_clock::now().time_since_epoch().count())
#define reset_timer _start_time=nano
#define chime cout<<((nano-_start_time)/1e9)<<endl
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))

#ifndef ONLINE_JUDGE
#define debug(x) (cout<<(#x)<<':'<<(x)<<'\n')
#else
#define debug(x)
#endif

void yesno(bool a) {
	cout << (a ? "Yes\n" : "No\n");
}

template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template<typename T1, typename T2, typename T3>
ostream& operator<<(ostream& out, const tuple<T1, T2, T3>& tp) {
	auto &[t1, t2, t3] = tp;
	out << '(' << t1 << ',' << t2 << ',' << t3 << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const unordered_set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

namespace segtree_single_point{
#define sti segtree<int>
#define stl segtree<ll>
	
	template<typename T>
	auto lambda_add=[](T &x,T &y)->T{
		return x+y;
	};
	
	template<typename T>
	auto lambda_min=[](T &x,T &y)->T{
		return x<y?x:y;
	};
	
	template<typename T>
	auto lambda_max=[](T &x,T &y)->T{
		return x>y?x:y;
	};
	
	template<typename T>
	auto lambda_min_max=[](const pair<T,T> &p1,const pair<T,T> &p2)->pair<T,T>{
		return {min(p1.first,p2.first),max(p1.second,p2.second)};
	};
	
	template<typename T>
	class segtree{
	public:
		segtree(const vector<T> &source, function<T(T&,T&)> merger, T defaultValue=(T)0){
			this->merger=merger;
			this->defaultValue=defaultValue;
			int n=source.size();
			int L=1;
			while(L<n) L<<=1;
			size=L;
			vector<T> v(2*L,defaultValue);
			data=v;
			for(int i=0;i<n;i++) data[L+i]=source[i];
			for(int i=L-1;i>=1;i--) data[i]=merge(data[2*i],data[2*i+1]);
		}
		
		T get(int index){
			return data[size+index];
		}
		
		void add(int index,T value){
			put(index,data[size+index]+value);
		}
		
		void put(int index,T value){
			_put(size+index,value);
		}
		
		//查询闭区间[l,r]
		T query(int l,int r){
			return _query(1,0,size,l,r+1);
		}
		
		
		/*查找在l右边的，离l最远的坐标r，使得query(l,r)满足条件。
		  需要ok函数满足二分查找性质：即当r>l时，ok(query(l,r))-->ok(query(l,r+1))。
		  找不到则返回-1。
		  @param l 二分查找的起点。
		  @param ok 判断某个区间是否合法的函数。
		  @return 查找到的在l右边的，离l最远的坐标，使得ok(query(l,r))==true。
		  如果找不到，返回-1。
		 */
		int find_from(int l, const function<bool(T)> &ok){
			T prev=defaultValue;
			return _find_from(1,0,size,l,ok,prev);
		}
		
		void show(){
			cout<<data;
		}
		
	private:
		vector<T> data;
		function<T(T&,T&)> merger;
		int size;
		T defaultValue;
		
		T merge(T left,T right){
			return merger(left,right);
		}
		
		void _put(int i,T value){
			data[i]=value;
			if(i==1) return;
			int j=i^1;
			if(i>j) swap(i,j);
			_put(i>>1,merge(data[i],data[j]));
		}
		
		T _query(int index,int L,int R,int l,int r){
			if(L>=r || R<=l) return defaultValue;
			//			int index=(size+L)/(R-L);
			if(index>=size) {
				return data[index];
			}
			if(L>=l && R<=r) {
				return data[index];
			}
			int mid=(L+R)>>1;
			T ans=defaultValue;
			if(r>L) ans=merge(ans,_query(2*index,L,mid,l,r));
			if(l<R) ans=merge(ans,_query(2*index+1,mid,R,l,r));
			return ans;
		}
		
		int _find_from(int index,int L,int R,int l, const function<bool(T)> &ok,T &prev){
			if(R<=l) return -1;
			T after_merge=merge(prev,data[index]);
			bool this_ok=ok(after_merge);
			if(index>=size){
				if(this_ok){
					prev=after_merge;
					return L;
				}else return -1;
			}
			if(L>=l && this_ok) {
				prev=after_merge;
				return R-1;
			}
			int mid=(L+R)>>1;
			if(mid<=l) return _find_from(2*index+1,mid,R,l,ok,prev);
			int ans=-1;
			ans=max(ans,_find_from(2*index,L,mid,l,ok,prev));
			if(ans==mid-1) {
				ans=max(ans,_find_from(2*index+1,mid,R,l,ok,prev));
			}
			return ans;
		}
	};
}

using namespace segtree_single_point;

ll mod;

const int MAX=100005;
ll x[MAX];
ll y[MAX];
ll z[MAX];


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,q;
	cin>>n>>mod>>q;
	x[0]=y[0]=z[0]=1;
	for(int i=1;i<MAX;i++){
		x[i]=(x[i-1]+1)%mod;
		y[i]=(3*y[i-1]+2*x[i]*z[i-1])%mod;
		z[i]=(3*z[i-1])%mod;
	}
	vi v(n+1,0);
	sti st(v,lambda_add<int>);
	while(q--){
		int L,M,R;
		cin>>L>>M>>R;
		st.add(L,1);
		if(R<n) st.add(R+1,-1);
		int t=st.query(1,M);
		cout<<x[t]<<sp<<y[t]<<sp<<z[t]<<nl;
	}
}

yukicoder

結果

テストケース

ソースコード