QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812157#7329. Independent Eventszhenjianuo2025WA 1482ms8220kbC++146.3kb2024-12-13 12:05:022024-12-13 12:05:02

Judging History

This is the latest submission verdict.

  • [2024-12-13 12:05:02]
  • Judged
  • Verdict: WA
  • Time: 1482ms
  • Memory: 8220kb
  • [2024-12-13 12:05:02]
  • 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<bits/stdc++.h>
// #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();
	}
};
/*

*/
int n,m;
double a[MAXN];
class SegTree{
public:
	int l,r;
	double sum;
	double tg;	
}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 update(int p,double k){
	tr[p].sum*=k;
	tr[p].tg*=k;
}
void push_down(int p){
	if(tr[p].tg!=1){
		update(lc(p),tr[p].tg);
		update(rc(p),tr[p].tg);
		tr[p].tg=1;
	}
}
void Build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	tr[p].sum=0;
	tr[p].tg=1;
	if(l==r){
		tr[p].sum=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 Modify(int p,int l,int r,double k){
	if(l<=tr[p].l && tr[p].r<=r){
		update(p,k);
		return ;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid)	Modify(lc(p),l,r,k);
	if(r>mid)	Modify(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;
}
double ln(double x){
    return log(x);
}
const int B=10;

void solve(bool SPE){ 
	while(cin>>n){
		// assert(n>=B);
		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;
				Modify(1,l,r,k);
			}else{
				int l,r;
				cin>>l>>r;
				double ans=0;
				if(r-l+1<=2000){
					foru(i,l,r){
						double x=Query(1,i,i);
						ans+=ln(1.0-x);
					}
				}else{
					int i=l;
					for(;i+B-1<=r;i+=B){
						double x=Query(1,i,i+B-1)/(double)B;
						ans+=(double)B*ln(1.0-x);
					}
					for(;i<=r;i++){
						ans+=ln(1.0-Query(1,i,i));
					}
				}
				#undef double
				printf("%.20lf\n",(double)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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5896kb

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.16021487727848474081
-0.25587417689480757010
-0.14734347732072095027

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 161ms
memory: 6132kb

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.00094044207705666746
-0.17285693984128142064
-0.64724368410974253418
-0.00144732047221210144
-0.09295564190549820971
-0.93078328060097825780
-0.06410239318769475614
-0.09166404281803548770
-0.04774269239055688174
-0.00085018090138477365
-0.03185781098379997928
-0.23731222356479128588
-0.517538000...

result:

ok 49679 numbers

Test #3:

score: 0
Accepted
time: 65ms
memory: 5908kb

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.11234334353646578675
-0.06540972096058840501
-0.00070024511439339195
-0.00079031221444377008
-0.00042008822470378189
-0.03031012007523891869
-0.22314667967829177053
-0.23039835923016496744
-0.23109860434455833933
-0.06119075875847015955
-0.03442884130322685504
-0.19239907802427019812
-0.041068196...

result:

ok 49929 numbers

Test #4:

score: -100
Wrong Answer
time: 1482ms
memory: 8220kb

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.25383483182050170512
-1.20091333485136253501
-4.83376522734095548373
-6.51824680115526700064
-4.75304132895725839347
-6.78931476906469377752
-1.01552586349810392008
-0.92628338022877920732
-6.03469117983051628329
-2.98820177605649917041
-7.72666467593490402521
-1.08031515561991842134
-6.670126007...

result:

wrong answer 2520th numbers differ - expected: '-29.6481789677', found: '-29.6233319046', error = '0.0008380637'