oj.uz

Submission #40126

# Submission time Handle Problem Language Result Execution time Memory
40126 2018-01-27T17:59:54 Z alanm Garaža (COCI17_garaza) C++14
0 / 160
 4000 ms 20372 KB 
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <math.h>
#include <stack>
#include <limits.h>
#include <queue>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>
#include <deque>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#include <fstream>
#define REP(i,N)for(long long i=0;i<(N);i++)
#define FOR(i,a,b)for(long long i=(a);i<=(b);i++)
#define FORD(i,a,b)for(long long i=a;i>=(b);i--)
#define ll long long
#define vi vector<ll>
#define vii vector<pair<ll,ll> >
#define vvi vector<vector<ll> >
#define vb vector<bool>
#define pii pair<ll,ll>
#define ALL(x) (x).begin(), (x).end()
#define SZ(a)((ll)(a).size())
#define CHECK_BIT(n,x)((bool)((n)&(((ll)1)<<(x))))
#define pow2(x) ((x)*(x))
#define VELA 2000000009999999999ll
#define X first
#define Y second
using namespace std;

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	return (a%b==0?b:gcd(a%b,b));
}

struct Range {
	vii pre, suf;
	ll count;
};
vii Add(vii a, vii b) {
	vii res=a;
	res.insert(res.end(),ALL(b));
	FOR(i,1, SZ(res)-1) {
		res[i].second = gcd(res[i].second,res[i-1].second);
	}
	vii zip(1,res[0]);
	FOR(i,1 ,SZ(res)-1) {
		if (zip.back().second == res[i].second) {
			zip[SZ(zip) - 1].first = zip[SZ(zip) - 1].first + res[i].first;
		}
		else {
			zip.push_back(res[i]);
		}
	}
	return zip;
}

vii GetR(vii a) {
	vii res = a;
	reverse(ALL(res));
	return res;
}

Range Union(Range a, Range b) {
	Range res;
	res.pre = Add(a.pre, b.pre);
	res.suf = GetR(Add(GetR(b.suf), GetR(a.suf)));
	res.count = a.count + b.count;
	ll r=0;
	ll rSz=0;
	REP(l, SZ(a.suf)) {
		while (r < SZ(b.pre) && gcd(b.pre[r].second, a.suf[l].second)>1) {
			rSz += b.pre[r].first;
			r++;
		}
		res.count += (a.suf[l].first)*rSz;
	}
	return res;
}

struct Intervalac {
	vector<Range> tree;
	ll nListy = 2;
	Intervalac(ll n) {
		while (nListy < n + 2) {
			nListy *= 2;
		}
		tree = vector<Range>(2 * nListy, Range{ vii(1,{1,1}),vii(1,{1,1}),0 });
		FORD(i, nListy - 1, 1)tree[i] = Union(tree[i * 2], tree[i * 2 + 1]);
	}
	void Change(ll k, ll val) {
		k += nListy + 1;
		tree[k] = Range{ vii(1,{1,val}),vii(1,{1,val}),val>1?1:0};
		k /= 2;
		while (k > 0) {
			tree[k] = Union(tree[k*2ll],tree[k*2ll+1ll]);
			k /= 2;
		}
	}
	ll Get(ll l, ll r) {
		l += nListy;
		r += nListy + 2;
		Range res = Range{ vii(1, { 1,1 }), vii(1, {1,1}),0 };
		while (l / 2 != r / 2) {
			if (l % 2 == 0)res = Union(res, tree[l + 1]);
			if (r % 2 == 1)res = Union(res,tree[r-1]);
			l /= 2;
			r /= 2;
		}
		return res.count;
	}
};

int main() {
	cin.sync_with_stdio(0);
	ll n,q;
	cin >> n>>q;
	Intervalac is(n);
	REP(i, n) {
		ll val;
		cin >> val;
		is.Change(i, val);
	}
	while (q--) {
		ll typ;
		cin >> typ;
		if (typ == 1) {
			ll index, val;
			cin >> index>>val;
			is.Change(index - 1, val);
		}
		else {
			ll l, r;
			cin >> l >> r;
			cout << is.Get(l - 1, r - 1) << "\n";
		}
	}
	return 0;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 970 ms 11156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2762 ms 20372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 0 KB Execution timed out
2 Halted 0 ms 0 KB -