| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35375 |
2017-11-21T14:22:17 Z |
RockyB |
Garaža (COCI17_garaza) |
C++11 |
|
3313 ms |
10264 KB |
/// 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
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;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10264 KB |
Output is correct |
| 2 |
Correct |
26 ms |
10264 KB |
Output is correct |
| 3 |
Correct |
69 ms |
10264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
523 ms |
10264 KB |
Output is correct |
| 2 |
Correct |
343 ms |
10264 KB |
Output is correct |
| 3 |
Correct |
383 ms |
10264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1543 ms |
10264 KB |
Output is correct |
| 2 |
Correct |
1133 ms |
10264 KB |
Output is correct |
| 3 |
Correct |
939 ms |
10264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1679 ms |
10264 KB |
Output is correct |
| 2 |
Correct |
3313 ms |
10264 KB |
Output is correct |
| 3 |
Correct |
1816 ms |
10264 KB |
Output is correct |
