Submission #35375

#	Time	Username	Problem	Language	Result	Execution time	Memory
35375		RockyB	Garaža (COCI17_garaza)	C++11	160 / 160	3313 ms	10264 KiB

garaza

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int get_int() {
	char x = getchar();
	while (!isdigit(x)) x = getchar();
	int res = 0;
	while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
	return res;
}
void out(ll x) {
	if (x > 9) out(x / 10);
	putchar(x % 10 + '0');
}

int n, q;
int a[N];

int gcd(int x, int y) {
	while (y) {
		x %= y;
		swap(x, y);	
	}
	return x | y;
}
struct node {
	ll sum;
	int val;
	node() {}
	node(ll sum, int val) : sum(sum), val(val) {}

	node operator + (const node &x) {
		return node(sum + x.sum, gcd(val, x.val));
	}	
};
struct tree {
	#define ls(v) (v << 1)
	#define rs(v) (v << 1 | 1)
	int u[N << 2];
	node t[N << 2];
	inline void build(int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			t[v].val = a[tl];
			return;
		}
		int tm = tl + tr >> 1;
		build(ls(v), tl, tm);
		build(rs(v), tm + 1, tr);
		t[v] = t[ls(v)] + t[rs(v)];
	}
	inline void push(int v, int tl, int tr) {
		if (u[v]) {
			int tm = tl + tr >> 1;
			t[ls(v)].sum = (ll)(tm - tl + 1) * u[v];
			t[rs(v)].sum = (ll)(tr - tm) * u[v];
			u[ls(v)] = u[rs(v)] = u[v];
			u[v] = 0;
		}
	}
	inline node get(int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (l <= tl && tr <= r) return t[v];
		int tm = tl + tr >> 1;
		push(v, tl, tr);
		if (tm < l) return get(l, r, rs(v), tm + 1, tr);
		if (r <= tm) return get(l, r, ls(v), tl, tm);
		return get(l, r, ls(v), tl, tm) + get(l, r, rs(v), tm + 1, tr);
	}
	inline int find_right(int x, int p) {
		if (x == 1) return p - 1;
		int l = p, r = n, res = l;
		while (l <= r) {
			int mid = l + r >> 1;
			if (get(p, mid).val > 1) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		return res;
	}
	inline void upd(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n) {
		if (l <= tl && tr <= r) {
			if (tp == 1) {
				u[v] = x;
				t[v].sum = (tr - tl + 1) * (ll)x;
			}
			else {
				t[v].val = x;
				t[v].sum = find_right(x, tl);
			}
			return;
		}
		int tm = tl + tr >> 1;
		push(v, tl, tr);
		if (tm < l) upd(l, r, x, tp, rs(v), tm + 1, tr);
		else if (r <= tm) upd(l, r, x, tp, ls(v), tl, tm);
		else {
			upd(l, r, x, tp, ls(v), tl, tm);
			upd(l, r, x, tp, rs(v), tm + 1, tr);
		}
		t[v] = t[ls(v)] + t[rs(v)];
	}
	
	inline void build1(int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			t[v].sum = find_right(a[tl], tl);
			return;
		}
		int tm = tl + tr >> 1;
		build1(ls(v), tl, tm);
		build1(rs(v), tm + 1, tr);
		t[v] = t[ls(v)] + t[rs(v)];
	}
	inline int find(int r, int x, int sh, int v = 1, int tl = 1, int tr = n) {
		if (r < tl) return -1;
		if (tl == tr) {
			if (gcd(x, a[tl]) == sh) return tl;
			return inf;
		}
		int tm = tl + tr >> 1;
		int on = gcd(x, t[rs(v)].val);

		if (on < sh) {
			int now = find(r, x, sh, rs(v), tm + 1, tr);
			if (now == -1) return find(r, x, sh, ls(v), tl, tm);
			return now;
		}
		return min(tm + 1, find(r, on, sh, ls(v), tl, tm));
	}


	#undef ls(v)
	#undef rs(v)
} t;


inline ll get(int l, int r) {
	return (ll)r * (r + 1) / 2 - (ll)l * (l + 1) / 2;
}
inline void solve(int L, int R) {
	int l = L, r = R, res = l - 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (t.get(mid, mid).sum <= R) res = mid, l = mid + 1;
		else r = mid - 1;
	}
	ll ans = 0;
	if (res >= L) ans = t.get(L, res).sum;
	ans -= get(L - 1, R) - (R - L + 1);
	ans += (ll)R * (R - res);
	out(ans);
	putchar('\n');
}
inline void upd(int p, int x) {
	a[p] = x;
	t.upd(p, p, x, 2);
	int l = 1, r = p, res = p;
	while (l <= r) {
		int mid = l + r >> 1;
		if (t.get(mid, mid).sum >= p) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (res < p) t.upd(res, p - 1, p - 1, 1);
	int cur = x, R = p;
	while (cur > 1 && R >= 1) {
		int l = t.find(R, cur, cur);
		t.upd(l, R, t.find_right(a[R], R), 1);
		if (l == 1 || l == inf) break;
		cur = gcd(cur, a[l - 1]);
		R = l - 1;
	}
}

int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		//freopen ("F.out", "w", stdout);
	#endif
	n = get_int(), q = get_int();
	for (int i = 1; i <= n; i++) {
		a[i] = get_int();
	}
	t.build();
	t.build1();
	for (int i = 1; i <= q; i++) {
		int t = get_int(), l = get_int(), r = get_int();
		if (t == 1) upd(l, r);
		else solve(l, r);
	}
	ioi
}

Compilation message (stderr)

garaza.cpp:159:11: warning: extra tokens at end of #undef directive
  #undef ls(v)
           ^
garaza.cpp:160:11: warning: extra tokens at end of #undef directive
  #undef rs(v)
           ^
garaza.cpp: In member function 'void tree::build(int, int, int)':
garaza.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
garaza.cpp: In member function 'void tree::push(int, int, int)':
garaza.cpp:83:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int tm = tl + tr >> 1;
                ^
garaza.cpp: In member function 'node tree::get(int, int, int, int, int)':
garaza.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
garaza.cpp: In member function 'int tree::find_right(int, int)':
garaza.cpp:102:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 1;
                ^
garaza.cpp: In member function 'void tree::upd(int, int, int, int, int, int, int)':
garaza.cpp:120:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
garaza.cpp: In member function 'void tree::build1(int, int, int)':
garaza.cpp:136:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
garaza.cpp: In member function 'int tree::find(int, int, int, int, int, int)':
garaza.cpp:147:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
garaza.cpp: In function 'void solve(int, int)':
garaza.cpp:170:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
               ^
garaza.cpp: In function 'void upd(int, int)':
garaza.cpp:186:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
               ^

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40
• Subtask 4: 40 / 40