QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#811622#7329. Independent Eventszhenjianuo2025WA 1674ms6772kbC++147.3kb2024-12-12 21:37:272024-12-12 21:37:28

Judging History

This is the latest submission verdict.

  • [2024-12-12 21:37:28]
  • Judged
  • Verdict: WA
  • Time: 1674ms
  • Memory: 6772kb
  • [2024-12-12 21:37:27]
  • Submitted

answer

//%^~
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
// #include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <limits>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// #include "ext/pb_ds/priority_queue.hpp"
// #include <ext/rope>
// #define PBDS __gnu_pbds
// #include <bits/extc++.h>
#define MAXN 200005
#define eps 1e-10
#define foru(a, b, c) for (int a = (b); (a) <= (c); (a)++)
#define ford(a, b, c) for (int a = (b); (a) >= (c); (a)++)
#define uLL unsigned long long
#define LL long long
#define LXF int
#define RIN Cap1taLDebug::read()
#define RSIN Cap1taLDebug::rdstr()
#define RCIN Cap1taLDebug::rdchar()
#define HH printf("\n")
// #define double long double
#define All(x) (x).begin(), (x).end()
#define fi first
#define se second
#define CA const auto&
using namespace std;
// const int RANDOM = time(0);
// template<class T1,class T2>
// class tr1::hash<pair<T1,T2>>{
// public:
	// size_t operator () (pair<T1,T2> x)const{
		// tr1::hash<T1> H1;
		// tr1::hash<T2> H2;
		// return H1(x.fi)^H2(x.se)^RANDOM;
	// }
// };
int ID;
class Cap1taLDebug{
	#ifdef LXF
	#define READTYPE LXF
	#else
	#define READTYPE int
	#endif
	#define DEBUGING
private:
	ostream& buf;
	#ifndef DEBUGING
	static char fbuf[1<<21],*p1,*p2;
	#define getchar() (Cap1taLDebug::p1==p2&&(p1=(p2=fbuf)+fread(fbuf,1,1<<21,stdin),p1==p2)?EOF:*p2++)
	#endif
public:
	Cap1taLDebug(ostream& out=cout):buf(out){}
	~Cap1taLDebug(){
		#ifdef DEBUGING
		buf.flush();
		#endif
	}
	static READTYPE read(){
		READTYPE x=0,w=1;char ch=0;
		while(!isdigit(ch)){
		if(ch=='-')	w=-1;
		ch=getchar();
		}
		while(isdigit(ch))	x=x*10+(ch^48),ch=getchar();
		return x*w;
	}
	static string rdstr(){
		string s;char c=getchar();
		while(c==' ' || c=='\r' || c=='\n')	c=getchar();	
		while(c!=' ' && c!='\r' && c!='\n' && c!=EOF)	s+=c,c=getchar();
		return s;
	}
	static char rdchar(){
		char c=getchar();
		while(c==' ' || c=='\r' || c=='\n')	c=getchar();
		return c;
	}
	static string int128ToString(__int128 x){
		if(x==0)	return "0";
		string s="",w="";
		if(x<0)	w="-",x*=-1;
		while(x) s+=(char)('0'+(int)(x%10)),x/=10;
		reverse(All(s));
		return w+s;
	}
	Cap1taLDebug& operator<<(const string val){
		#ifdef DEBUGING
		buf<<val;
		#endif
		return *this;
	}
	template<typename T1,typename T2>
	Cap1taLDebug& operator<<(const pair<T1,T2>& val){
		#ifdef DEBUGING
		(*this)<<"("<<val.first<<","<<val.second<<")";
		#endif
		return *this;
	}
	template<typename T,template<typename,typename...>class Container,typename...Args>
	Cap1taLDebug& operator<<(const Container<T, Args...>& container){
		#ifdef DEBUGING
		buf<<"{";
		bool fst=0;
		for(const auto& val:container){
			if(!fst)	fst=true;
			else	buf<<",";
			(*this)<<val;	
		}
		buf<<"}";
		#endif
		return *this;
	}
	Cap1taLDebug& operator<<(const __int128& val){
		#ifdef DEBUGING
		buf<<int128ToString(val);
		#endif
		return *this;
	}
	template<typename T>
	Cap1taLDebug& operator<<(const T& val){
		#ifdef DEBUGING
		buf<<val;
		#endif
		return *this;
	}
	Cap1taLDebug& operator<<(ostream& (*manip)(ostream&)){
		#ifdef DEBUGING
		buf<<manip;
		#endif
		return *this;
	}
};
#ifndef DEBUGING
char Cap1taLDebug::fbuf[1<<21],*Cap1taLDebug::p1=nullptr,*Cap1taLDebug::p2=nullptr;
#endif
Cap1taLDebug cein(cout);
// Cap1taLDebug cein(cerr);
ostream& operator<<(ostream& os,__int128 val){
	os<<Cap1taLDebug::int128ToString(val);
	return os;
}
template<typename T>
class Stack : public stack<T>{
public:
	void clear(){
		while(!this->empty())	this->pop();
	}
	void popuntil(const function<bool(T)>& func){
		while(!this->empty() && !func(this->top()))	this->pop();
	}
};
/*

*/
constexpr double E=exp(1);
constexpr double loge=log(E);
constexpr double ln(double x){
	return log(x)/loge;
}
constexpr double y=ln(0.9);

constexpr double K=(0.0-y)/(1.0-0.9);
constexpr double B=-K;
auto f=[](double x){
	return K*x+B;
};
auto g=[](double x){
	return x/K-B/K;
};
int n,m;
double a[MAXN];
class SegTree{
public:
	int l,r;
	double sum;
	double mul;
	double add;
}tr[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
void push_up(int p){
	tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
}
void updateadd(int p,double k){
	tr[p].sum+=k*(double)(tr[p].r-tr[p].l+1);
	tr[p].add+=k;
}
void updatemul(int p,double k){
	tr[p].sum*=k;
	tr[p].mul*=k;
	tr[p].add*=k;
}
void push_down(int p){
	if(tr[p].mul!=1){
		updatemul(lc(p),tr[p].mul);
		updatemul(rc(p),tr[p].mul);
		tr[p].mul=1;
	}
	if(tr[p].add!=0){
		updateadd(lc(p),tr[p].add);
		updateadd(rc(p),tr[p].add);
		tr[p].add=0;
	}
}
void Build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	tr[p].sum=0;
	tr[p].mul=1;
	tr[p].add=0;
	if(l==r){
		tr[p].sum=ln(1.0-a[l]);
		return ;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	Build(lc(p),l,mid);
	Build(rc(p),mid+1,r);
	push_up(p);
}
void Modifymul(int p,int l,int r,double k){
	if(l<=tr[p].l && tr[p].r<=r){
		updatemul(p,k);
		return ;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid)	Modifymul(lc(p),l,r,k);
	if(r>mid)	Modifymul(rc(p),l,r,k);
	push_up(p);
}
void Modifyadd(int p,int l,int r,double k){
	if(l<=tr[p].l && tr[p].r<=r){
		updateadd(p,k);
		return ;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid)	Modifyadd(lc(p),l,r,k);
	if(r>mid)	Modifyadd(rc(p),l,r,k);
	push_up(p);
}
double Query(int p,int l,int r){
	if(l<=tr[p].l && tr[p].r<=r)	return tr[p].sum;
	int mid=(tr[p].l+tr[p].r)>>1;
	double ret=0;
	push_down(p);
	if(l<=mid)	ret+=Query(lc(p),l,r);
	if(r>mid)	ret+=Query(rc(p),l,r);
	return ret;
}
const int L=1000;
void solve(bool SPE){ 
	
	// for(double i=0.9;i<=1;i+=0.005){
		// double x=ln(i);
		// double y=f(i);
		// cout<<x<<' '<<y<<endl;
		// cout<<exp(x)<<' '<<g(y)<<endl;
	// }
	// cout<<ln(-8);
	while(cin>>n){
		cin>>m;
		foru(i,1,n){
			cin>>a[i];
		}
		Build(1,1,n);
		while(m--){
			int opt;
			cin>>opt;
			if(opt==1){
				int l,r;
				double k;
				cin>>l>>r>>k;
				
				//(1-p)*k+1-k
				
				if(r-l+1<=L){
					foru(i,l,r){
						double x=Query(1,i,i);
						x=ln(exp(x)*k+1-k)-x;
						Modifyadd(1,i,i,x);
					}
				}else{
					Modifymul(1,l,r,k);
					Modifyadd(1,l,r,(B+K)*(1.0-k));
				}
				
				//ln(xc)=ln(x)+ln(c)
				
				// double c=1-k;
				// //f(x+c)=K(x+c)+b=Kx+b+Kc
				// // Modifyadd(1,l,r,K*c);
// 				
				
				
			}else{
				int l,r;
				cin>>l>>r;
				double ans=0;
				
				ans=Query(1,l,r);
				// #undef double
				printf("%.14lf\n",ans);
			}
		}
		
	}
	
	#ifdef DEBUGING
	if(SPE){
		
	}
	#endif
	return ;
}
/*
检查文件读写
检查多测清空
检查数组大小
*/
signed main()
{
	// #define RFILE
	// #define MULTITEST
	// #define TESTCASEID
	
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	#ifdef RFILE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	
	#ifdef MULTITEST
	int T=RIN;
	#else
	int T=1;
	#endif
	
	#ifdef TESTCASEID
	ID=RIN;
	#endif
	
	for(int i=1;i<=T;i++) solve(i==0);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6184kb

input:

6 5
0.01000 0.09871 0.00005 0.00999 0.01234 0.02345
0 1 6
1 3 4 10.00000
0 1 6
1 1 2 0.05000
0 1 6

output:

-0.16021487727848
-0.25587417689481
-0.14734347732072

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 178ms
memory: 6212kb

input:

54 36
0.00014 0.00020 0.00054 0.00084 0.00088 0.00095 0.00031 0.00077 0.00054 0.00050 0.00024 0.00057 0.00066 0.00029 0.00084 0.00031 0.00024 0.00091 0.00063 0.00069 0.00024 0.00041 0.00090 0.00057 0.00071 0.00031 0.00047 0.00016 0.00063 0.00074 0.00040 0.00077 0.00058 0.00049 0.00013 0.00076 0.0007...

output:

-0.00094044207706
-0.17285693984128
-0.64724368410973
-0.00144732047221
-0.09295564190550
-0.93078328060098
-0.06410239318769
-0.09166404281803
-0.04774269239055
-0.00085018090138
-0.03185781098380
-0.23731222356479
-0.51753800054858
-0.65349942535262
-0.30108917501326
-0.06242231872180
-0.476679973...

result:

ok 49679 numbers

Test #3:

score: 0
Accepted
time: 67ms
memory: 4220kb

input:

13 5
0.00046 0.00033 0.00056 0.00093 0.00039 0.00094 0.00096 0.00085 0.00059 0.00083 0.00032 0.00075 0.00036
1 4 6 46.93710
0 3 11
0 5 8
1 4 13 2.21652
1 4 8 0.13103
4 14
0.00070 0.00028 0.00042 0.00079
0 1 1
0 4 4
0 3 3
1 2 2 100.00000
0 1 4
1 2 3 1.93082
1 3 4 100.00000
0 1 4
1 2 4 1.03435
0 2 4
0...

output:

-0.11234334353647
-0.06540972096059
-0.00070024511439
-0.00079031221444
-0.00042008822470
-0.03031012007523
-0.22314667967827
-0.23039835923014
-0.23109860434454
-0.06119075875847
-0.03442884130323
-0.19239907802429
-0.04106819600668
-0.08834249429540
-0.02770611865525
-0.00139256082018
-0.002030963...

result:

ok 49929 numbers

Test #4:

score: -100
Wrong Answer
time: 1674ms
memory: 6772kb

input:

625 1069
0.00107 0.00141 0.00178 0.00124 0.00104 0.00133 0.00188 0.00168 0.00108 0.00183 0.00199 0.00171 0.00122 0.00170 0.00133 0.00188 0.00128 0.00186 0.00165 0.00190 0.00117 0.00137 0.00129 0.00152 0.00136 0.00137 0.00135 0.00137 0.00134 0.00160 0.00159 0.00134 0.00124 0.00191 0.00193 0.00122 0.0...

output:

-5.25383483182049
-1.20091333485136
-4.83376522734098
-6.51824680115529
-4.75304132895728
-6.78931476906472
-1.01552586349810
-0.92628338022878
-6.03469117983053
-2.98820177605650
-7.72666467593491
-1.08031515561993
-6.67012600705670
-2.18541217642486
-5.15756517083218
-8.41424996371343
-1.800305927...

result:

wrong answer 559th numbers differ - expected: '-17.8312289323', found: '-18.1746831027', error = '0.0192613853'