# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
473335 |
2021-09-15T12:24:00 Z |
AbdoMo |
Garaža (COCI17_garaza) |
C++17 |
|
4000 ms |
1476 KB |
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
const int mod = 1e9+7;
using namespace std;
bool comp(string a,string b)
{
if(a.size()==b.size())
{
return a<b;
}
return a.size()<b.size();
}
int arr[100005];
int n,q;
int ggcd(int l,int r)
{
int x=0;
for(int i=l;i<=r;i++)
{
x=__gcd(x,arr[i]);
}
return x;
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
while(q--)
{
int x,l,r;
cin>>x>>l>>r;
if(x == 1)
{
arr[l]=r;
}
else
{
int gg=0;
int c=0;
int ans=0;
for(int i=l;i<=r;i++)
{
int s=i,e=r,m;
int lst=i;
if(arr[i]==1)continue;
while(s<=e)
{
m=(s+e)/2;
if(ggcd(i,m)>1)
{
s=m+1;
lst=m;
}
else
{
e=m-1;
}
}
ans+=lst-i+1;
}
cout<<ans<<endl;
}
}
}
int32_t main(){
int t=1;
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// cin>>t;
while(t--){solve();}
return 0;
}
Compilation message
garaza.cpp: In function 'void solve()':
garaza.cpp:45:17: warning: unused variable 'gg' [-Wunused-variable]
45 | int gg=0;
| ^~
garaza.cpp:46:17: warning: unused variable 'c' [-Wunused-variable]
46 | int c=0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
712 ms |
332 KB |
Output is correct |
2 |
Execution timed out |
4070 ms |
332 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4097 ms |
716 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4067 ms |
972 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4088 ms |
1476 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |