| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 36533 |
2017-12-10T10:09:41 Z |
szawinis |
Garaža (COCI17_garaza) |
C++14 |
|
1753 ms |
37736 KB |
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
using ll = long long;
const int N = 1 << 17;
int n, q, a[N], lb[2*N], rb[2*N];
ll t[2*N];
vector<pair<int,int> > pref[2*N], suff[2*N];
void build(int pos, int l, int r) {
lb[pos] = l; rb[pos] = r;
if(l == r) {
pref[pos] = suff[pos] = {{a[l], l}};
t[pos] = a[l] > 1;
return;
}
int mid = l+r >> 1;
build(pos<<1, l, mid);
build(pos<<1|1, mid+1, r);
// init t
t[pos] = t[pos<<1] + t[pos<<1|1];
// cout << pos << ' ' << l << ' ' << r << ' ' << t[pos] << endl;
for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
while(j >= 0 && __gcd(suff[pos<<1][j].fs, pref[pos<<1|1][i].fs) == 1) --j;
if(j < 0) continue;
ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
t[pos] += res;
// cout << res << endl;
}
// init pref
pref[pos] = pref[pos<<1];
for(int i = 0; i < pref[pos<<1|1].size(); i++) {
int new_gcd = __gcd(pref[pos<<1|1][i].fs, pref[pos<<1].back().fs);
if(new_gcd != pref[pos].back().fs)
pref[pos].emplace_back(new_gcd, pref[pos<<1|1][i].sc);
}
// for(int i = 0; i < pref[pos].size(); i++) cout << pref[pos][i].fs << ' ' << pref[pos][i].sc << endl;
// init suff
suff[pos] = suff[pos<<1|1];
for(int i = 0; i < suff[pos<<1].size(); i++) {
int new_gcd = __gcd(suff[pos<<1][i].fs, suff[pos<<1|1].back().fs);
if(new_gcd != suff[pos].back().fs)
suff[pos].emplace_back(new_gcd, suff[pos<<1][i].sc);
}
// cout << endl;
// for(int i = 0; i < suff[pos].size(); i++) cout << suff[pos][i].fs << ' ' << suff[pos][i].sc << endl;
// cout << pos << ' ' << l << ' ' << r << ' ' << t[pos] << endl;
// cout << endl;
}
void update(int pos, int l, int r, int idx, int v) {
if(l == r) {
pref[pos] = suff[pos] = {{v, l}};
t[pos] = v > 1;
return;
}
int mid = l+r >> 1;
if(idx <= mid) update(pos<<1, l, mid, idx, v);
else update(pos<<1|1, mid+1, r, idx, v);
// update t
t[pos] = t[pos<<1] + t[pos<<1|1];
for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
while(j >= 0 && __gcd(suff[pos<<1][j].fs, pref[pos<<1|1][i].fs) == 1) --j;
if(j < 0) continue;
ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
t[pos] += res;
}
// update pref
pref[pos] = pref[pos<<1];
for(int i = 0; i < pref[pos<<1|1].size(); i++) {
int new_gcd = __gcd(pref[pos<<1|1][i].fs, pref[pos<<1].back().fs);
if(new_gcd != pref[pos].back().fs)
pref[pos].emplace_back(new_gcd, pref[pos<<1|1][i].sc);
}
// update suff
suff[pos] = suff[pos<<1|1];
for(int i = 0; i < suff[pos<<1].size(); i++) {
int new_gcd = __gcd(suff[pos<<1][i].fs, suff[pos<<1|1].back().fs);
if(new_gcd != suff[pos].back().fs)
suff[pos].emplace_back(new_gcd, suff[pos<<1][i].sc);
}
}
ll query(int l, int r) {
int tmpl = l, tmpr = r;
ll ret = 0;
vector<int> segs;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) {
ret += t[l];
segs.push_back(l);
++l;
}
if(r & 1) {
--r;
ret += t[r];
segs.push_back(r);
}
}
l = tmpl, r = tmpr;
sort(segs.begin(), segs.end(), [] (int i, int j) { return lb[i] < lb[j]; });
vector<pair<int,int> > loc_suff;
for(int pos: segs) {
for(int i = 0, j = loc_suff.size()-1; i < pref[pos].size(); i++) {
while(j >= 0 && __gcd(loc_suff[j].fs, pref[pos][i].fs) == 1) --j;
if(j < 0) continue;
ll res = lb[pos]-1 - (j < loc_suff.size()-1 ? loc_suff[j+1].sc : l-1);
res *= (i < pref[pos].size()-1 ? pref[pos][i+1].sc : rb[pos]+1) - pref[pos][i].sc;
ret += res;
}
vector<pair<int,int> > tmp = suff[pos];
for(int i = 0; i < loc_suff.size(); i++) {
int new_gcd = __gcd(loc_suff[i].fs, suff[pos].back().fs);
if(new_gcd != tmp.back().fs)
tmp.emplace_back(new_gcd, loc_suff[i].sc);
}
loc_suff = tmp;
}
return ret;
}
int main() {
scanf("%d %d", &n, &q);
fill(a, a+N, 1);
for(int i = 0; i < n; i++) scanf("%d", a+i);
build(1, 0, N-1);
while(q--) {
int type; cin >> type;
if(type == 1) {
int idx, v; scanf("%d %d", &idx, &v); --idx;
update(1, 0, N-1, idx, v);
} else {
int l, r; scanf("%d %d", &l, &r); --l; --r;
printf("%lld\n", query(l, r));
}
}
}
Compilation message
garaza.cpp: In function 'void build(int, int, int)':
garaza.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
garaza.cpp:25:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
^
garaza.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
^
garaza.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
^
garaza.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pref[pos<<1|1].size(); i++) {
^
garaza.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < suff[pos<<1].size(); i++) {
^
garaza.cpp: In function 'void update(int, int, int, int, int)':
garaza.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
garaza.cpp:65:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
^
garaza.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
^
garaza.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
^
garaza.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pref[pos<<1|1].size(); i++) {
^
garaza.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < suff[pos<<1].size(); i++) {
^
garaza.cpp: In function 'll query(int, int)':
garaza.cpp:108:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0, j = loc_suff.size()-1; i < pref[pos].size(); i++) {
^
garaza.cpp:111:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll res = lb[pos]-1 - (j < loc_suff.size()-1 ? loc_suff[j+1].sc : l-1);
^
garaza.cpp:112:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
res *= (i < pref[pos].size()-1 ? pref[pos][i+1].sc : rb[pos]+1) - pref[pos][i].sc;
^
garaza.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < loc_suff.size(); i++) {
^
garaza.cpp: In function 'int main()':
garaza.cpp:127:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &q);
^
garaza.cpp:129:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < n; i++) scanf("%d", a+i);
^
garaza.cpp:134:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int idx, v; scanf("%d %d", &idx, &v); --idx;
^
garaza.cpp:137:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int l, r; scanf("%d %d", &l, &r); --l; --r;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
35288 KB |
Output is correct |
| 2 |
Correct |
116 ms |
35420 KB |
Output is correct |
| 3 |
Correct |
116 ms |
35420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
35940 KB |
Output is correct |
| 2 |
Correct |
546 ms |
35816 KB |
Output is correct |
| 3 |
Correct |
389 ms |
35552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
799 ms |
36464 KB |
Output is correct |
| 2 |
Correct |
1219 ms |
36196 KB |
Output is correct |
| 3 |
Correct |
953 ms |
35812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1403 ms |
36868 KB |
Output is correct |
| 2 |
Correct |
1753 ms |
37736 KB |
Output is correct |
| 3 |
Correct |
1679 ms |
36204 KB |
Output is correct |
