QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745473 | #9738. Make It Divisible | hanmx | Compile Error | / | / | C++17 | 2.5kb | 2024-11-14 10:13:48 | 2024-11-14 10:13:48 |
Judging History
你现在查看的是最新测评结果
- [2024-11-27 18:44:44]
- hack成功,自动添加数据
- (/hack/1263)
- [2024-11-14 10:13:48]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2024-11-14 10:13:48]
- 提交
answer
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
using u64=unsigned long long;
template<class T>
T func(T x,T y){
return gcd(x,y);
}
template <class T>
struct SparseTable {
int n;
vector<vector<T>> a;
SparseTable(const vector<T> &init) : n(init.size()){
int lg = __lg(n);
a.assign(lg + 1, vector<T>(n));
a[0] = init;
for (int i = 1; i <= lg; i++) {
for (int j = 0; j <= n - (1 << i); j++) {
a[i][j] = func(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
}
}
}
T get(int l, int r) { // [l, r)
l--;
int lg = __lg(r - l);
return func(a[lg][l], a[lg][r - (1 << lg)]);
}
};
void solve(){
ll n,k;
cin>>n>>k;
vector<int> a(n+1);
vector<int> b(n);
int mn=1e9;
for(int i=1;i<=n;i++){
cin>>a[i];
mn=min(a[i],mn);
}
if(n==1){
cout<<k<<" "<<k*(k+1)/2<<'\n';
return;
}
for(int i=2;i<=n;i++){
b[i-2]=a[i]-a[i-1];
}
SparseTable<int> st(b);
vector<int> sta;
vector<int> l(n+1,1);
vector<int> r(n+1,n);
for(int i=1;i<=n;i++){
while(!sta.empty()&&a[sta.back()]>a[i]) sta.pop_back();
if(sta.size()){
if(sta.back()==1){
l[i]=sta.back()+1;
}
else l[i]=i;
sta.push_back(i);
}
sta.clear();
for(int i=n;i>=1;i--){
while(!sta.empty()&&a[sta.back()]>a[i]) sta.pop_back();
if(sta.size()) {
r[i]=sta.back()-1;
}
else r[i]=i;
sta.push_back(i);
}
vector<pair<int,int>> p;
for(int i=1;i<=n;i++){
if(l[i]==r[i]) p.push_back({a[i],a[i]});
else p.push_back({a[i],st.get(l[i],r[i]-1)});
}
int mx=st.get(1,n-1);
set<int> s;
for(int i=1;i<=sqrt(mx);i++){
if(mx%i==0){
int x=mx/i;
int y=i;
if(x-mn<=k&&x!=mn) s.insert(x-mn);
if(y-mn<=k&&y!=mn) s.insert(y-mn);
}
}
for(auto [x,y]:p){
for(auto z:s){
if(x==y) continue;
if(y%(x+z)==0) continue;
else s.erase(z);
}
}
cout<<s.size()<<" ";
ll ans=0;
for(auto x:s){
ans+=x;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--) solve();
return 0;
}
Details
answer.code:1:1: error: ‘answer’ does not name a type 1 | answer | ^~~~~~ In file included from /usr/include/c++/13/bits/stl_algobase.h:62, from /usr/include/c++/13/algorithm:60, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from answer.code:2: /usr/include/c++/13/ext/type_traits.h:164:35: error: ‘constexpr const bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity 164 | __is_null_pointer(std::nullptr_t) | ^ /usr/include/c++/13/ext/type_traits.h:159:5: note: previous declaration ‘template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)’ 159 | __is_null_pointer(_Type) | ^~~~~~~~~~~~~~~~~ /usr/include/c++/13/ext/type_traits.h:164:26: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’? 164 | __is_null_pointer(std::nullptr_t) | ^~~~~~~~~ In file included from /usr/include/c++/13/cstddef:50, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:41: /usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here 443 | typedef decltype(nullptr) nullptr_t; | ^~~~~~~~~ In file included from /usr/include/c++/13/bits/stl_pair.h:60, from /usr/include/c++/13/bits/stl_algobase.h:64: /usr/include/c++/13/type_traits:510:26: error: ‘std::size_t’ has not been declared 510 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/13/type_traits:511:25: error: ‘_Size’ was not declared in this scope 511 | struct is_array<_Tp[_Size]> | ^~~~~ /usr/include/c++/13/type_traits:511:31: error: template argument 1 is invalid 511 | struct is_array<_Tp[_Size]> | ^ /usr/include/c++/13/type_traits:617:33: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’? 617 | struct is_null_pointer<std::nullptr_t> | ^~~~~~~~~ /usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here 443 | typedef decltype(nullptr) nullptr_t; | ^~~~~~~~~ /usr/include/c++/13/type_traits:617:42: error: template argument 1 is invalid 617 | struct is_null_pointer<std::nullptr_t> | ^ /usr/include/c++/13/type_traits:621:48: error: template argument 1 is invalid 621 | struct is_null_pointer<const std::nullptr_t> | ^ /usr/include/c++/13/type_traits:625:51: error: template argument 1 is invalid 625 | struct is_null_pointer<volatile std::nullptr_t> | ^ /usr/include/c++/13/type_traits:629:57: error: template argument 1 is invalid 629 | struct is_null_pointer<const volatile std::nullptr_t> | ^ /usr/include/c++/13/type_traits:1348:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’? 1348 | : public integral_constant<std::size_t, alignof(_Tp)> | ^~~~~~ /usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here 214 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ /usr/include/c++/13/type_traits:1348:57: error: template argument 1 is invalid 1348 | : public integral_constant<std::size_t, alignof(_Tp)> | ^ /usr/include/c++/13/type_traits:1348:57: note: invalid template non-type parameter /usr/include/c++/13/type_traits:1357:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’? 1357 | : public integral_constant<std::size_t, 0> { }; | ^~~~~~ /usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here 214 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ /usr/include/c++/13/type_traits:1357:46: error: template argument 1 is invalid 1357 | : public integral_constant<std::size_t, 0> { }; | ^ /usr/include/c++/13/type_traits:1357:46: note: invalid template non-type parameter /usr/include/c++/13/type_traits:1359:26: error: ‘std::size_t’ has not been declared 1359 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/13/type_traits:1360:21: error: ‘_Size’ was not declared in this scope 1360 | struct rank<_Tp[_Size]> | ^~~~~ /usr/include/c++/13/type_traits:1360:27: error: template argument 1 is invalid 1360 | struct rank<_Tp[_Size]> | ^ /usr/include/c++/13/type_traits:1361:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t...