oj.uz

답안 #473227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473227 2021-09-15T10:40:58 Z SaraMostafa Garaža (COCI17_garaza) C++14
0 / 160
 4000 ms 1100 KB 
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define endl "\n"
#define Sara ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const long long mod=1e9+7;
const double PI=acos(-1);
// 1 2 3 --> 1,2,3 ...1,2..1,3..1..2,3..2..3..none (2 power number of elements)
//1 2 3 --> 2--> 1,2..1,3..2,3..(!n/(r!(n-r)!)) aka:ncr
// 1 2 3 -->2-->1,2..2,1..1,3..3,1..2,3..3,2..(n!/(n-r)!) aka:npr
//1 2 3--> 1..1,2..1,2,3..2..2,3..3  number of subarrays -->(n*(n+1))/2 "sum of numbers from 1 to n."
/*
ll power(ll x,ll y)
{
    if(y==0)
        return 1;
    else if(y==1)
        return x%mod;
    ll  r=power(x%mod,((y%mod)/2)%mod);
    if(y%2==0)
        return ((r%mod)*(r%mod));
    else
        return ((r%mod)*(r%mod)*(x%mod));
}

ll inverse(ll md,ll x)
{
    return power(x%mod,mod-2);
}

*/
int main()
{
    //freopen("input.in","r",stdin);

    Sara
    int n,q;
    cin>>n>>q;
    vector<ll>v(n);
    for(int i=0; i<n; i++)
    {
        cin>>v[i];
    }
    while(q--)
    {
        int o;
        cin>>o;
        if(o==1)
        {
            ll x,val;
            cin>>x>>val;
            x--;
            v[x]=val;
        }
        else
        {
            ll l,r;
            cin>>l>>r;
            l--;
            r--;
            ll cnt=0;
            for(int i=l; i<=r; i++)
            {
                ll gcd=v[i];
                for(int j=i; j<=r; j++)
                {
                    if(__gcd(v[j],gcd)>1)
                    {
                        gcd=__gcd(gcd,v[j]);
                        cnt++;
                    }
                    else break;
                }
            }
            cout<<cnt<<endl;

        }
    }
    return 0;
}

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 204 KB Output is correct
2 Execution timed out 4075 ms 204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4090 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4054 ms 588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4053 ms 1100 KB Time limit exceeded
2 Halted 0 ms 0 KB -