oj.uz

Submission #332553

# Submission time Handle Problem Language Result Execution time Memory
332553 2020-12-02T20:47:05 Z freitas Garaža (COCI17_garaza) C++14
0 / 160
 4000 ms 1772 KB 
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);
#define endl '\n'
#define INF 0x3f3f3f3f
#define OUT -1
#define MOD 1000000007
#define MAX (1<<20)
#define MAXN (1<<10)
#define MAXC (1<<10)
#define ll long long
#define all(x) (x).begin() , (x).end()
#define sz(x) (int)(x).size()
#define ii pair<int, int>
#define fs first
#define sc second
#define eb emplace_back
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<ii>
#define vvii vector<vii>
#define lsb(x) ((x) & (-x))
#define gcd(x,y) __gcd((x),(y))
#define esq(x) (x*2)
#define dir(x) ((x*2)+1)

using namespace std;

int n, seg3[MAX], a[MAX];

ll mdc(ll a, ll b){
	if(b == 0) return a;
	return (mdc(b, a%b));
}

ll merge(ll a, ll b){
	return mdc(max(a, b), min(a, b));
}

void biuld(int u, int l, int r){
	if(l == r){
		seg3[u] = a[l];
		return;
	}

	int md = ((l+r)/2);

	biuld(esq(u), l, md);
	biuld(dir(u), md+1, r);

	seg3[u] = merge(seg3[esq(u)] , seg3[dir(u)]);
}

void update(int u, int l, int r, int idx, int val){
	if(l == r){
		seg3[u] = val, a[idx] = val;
		return;
	}

	int md = (l+r)/2;

	if(l <= idx && idx <= md) update(esq(u), l, md, idx, val);
	if(md < idx && idx <= r) update(dir(u), md+1, r, idx, val);

	seg3[u] = merge(seg3[esq(u)], seg3[dir(u)]);
}

int query(int u, int i, int j, int l, int r){
	if(i >= l && r >= j) return seg3[u];
	if(l > j || i > r) return OUT;

	int md = (i+j)/2;

	int qa = query(esq(u), i, md, l, r);
	int qb = query(dir(u), md+1, j, l, r);

	if(qa == OUT) return qb;
	if(qb == OUT) return qa;

	return  merge(qa, qb);
}

int q, op, idx, l, r, val, t, ans;

int main(){_
	cin >> n >> q;
	for(int i = 1; n >= i; ++i){
		cin >> a[i];
	}

	biuld(1, 1, n);

	for(int k = 1; q >= k; ++k){
		cin >> op;
		if(op == 1){
			cin >> idx >> val;
			update(1, 1, n, idx, val);
		}
		if(op == 2){
			cin >> l >> r;
			ans = 0;
			for(int a = l; r >= a; ++a){
				for(int b = a; r >= b; ++b){
					if(query(1, 1, n, a, b) > 1) ++ans;
				}
			}
			cout << ans << endl;

		}
	}


	return 0;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4009 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4091 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 1004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4080 ms 1772 KB Time limit exceeded
2 Halted 0 ms 0 KB -