| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 156896 |
2019-10-08T07:01:54 Z |
IvanC |
Garaža (COCI17_garaza) |
C++17 |
|
1016 ms |
34048 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int MAXN = 1e5 + 10;
const int SEG_SZ = 262148;
inline int gcd(int a, int b){
if(b == 0) return a;
if(a < b) swap(a, b);
return gcd(b, a % b);
}
struct node{
int gcd_all;
vii pref, suf;
ll tot;
node(){
tot = 0;
gcd_all = 0;
}
node operator*(const node& other)const{
node ans;
ans.pref = pref;
ans.suf = other.suf;
ans.tot = tot + other.tot;
ans.gcd_all = gcd(gcd_all, other.gcd_all);
/*
printf("##############\n");
printf("Merging: %lld + %lld\n", tot, other.tot);
printf("Pref Left:");
for(ii davez: pref){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
printf("Suf Left:");
for(ii davez: suf){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
printf("Pref Right:");
for(ii davez: other.pref){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
printf("Suf Right:");
for(ii davez: other.suf){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
*/
for(int i = 0; i < other.pref.size(); i++){
int cand = gcd(gcd_all, other.pref[i].first);
if(cand == 1) break;
if(!ans.pref.empty() && ans.pref.back().first == cand){
ans.pref.back().second += other.pref[i].second;
}
else{
ans.pref.push_back(ii(cand, other.pref[i].second));
}
}
for(int i = 0; i < suf.size(); i++){
int cand = gcd(other.gcd_all, suf[i].first);
if(cand == 1) break;
ii novo = ii(cand, suf[i].second);
if(!ans.suf.empty() && ans.suf.back().first == cand){
ans.suf.back().second += suf[i].second;
}
else{
ans.suf.push_back(novo);
}
}
int j = 0, gcd_sum = 0;
for(int i = suf.size() - 1; i >= 0; i--){
while(j < other.pref.size() && gcd(suf[i].first, other.pref[j].first) > 1){
gcd_sum += other.pref[j].second;
j++;
}
ans.tot += 1LL*gcd_sum*suf[i].second;
//printf("DELTA %d %lld\n", i, 1LL*gcd_sum*suf[i].second);
}
/*
printf("Ans Pref:");
for(ii davez: ans.pref){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
printf("Ans Suf:");
for(ii davez: ans.suf){
printf(" (%d, %d)", davez.first, davez.second);
}
printf("\n");
printf("##############\n");
*/
return ans;
}
};
node seg[SEG_SZ];
int arr[MAXN], N, Q;
void build(int pos, int left, int right){
if(left == right){
seg[pos].pref.clear();
seg[pos].suf.clear();
seg[pos].gcd_all = arr[left];
if(arr[left] != 1){
seg[pos].tot = 1;
seg[pos].pref.push_back(ii(arr[left], 1));
seg[pos].suf.push_back(ii(arr[left], 1));
}
else{
seg[pos].tot = 0;
}
return;
}
int mid = (left+right)/2;
build(2*pos, left, mid);
build(2*pos+1, mid + 1, right);
seg[pos] = seg[2*pos]*seg[2*pos+1];
//printf("POS (%d, %d, %d) = %lld\n", pos, left, right, seg[pos].gcd_all);
}
void update(int pos, int left, int right, int x){
if(left == right){
seg[pos].pref.clear();
seg[pos].suf.clear();
seg[pos].gcd_all = arr[left];
if(arr[left] != 1){
seg[pos].tot = 1;
seg[pos].pref.push_back(ii(arr[left], 1));
seg[pos].suf.push_back(ii(arr[left], 1));
}
else{
seg[pos].tot = 0;
}
return;
}
int mid = (left+right)/2;
if(x <= mid) update(2*pos, left, mid, x);
else update(2*pos+1, mid + 1, right, x);
seg[pos] = seg[2*pos]*seg[2*pos+1];
}
node query(int pos, int left, int right, int i, int j){
if(left >= i && right <= j){
return seg[pos];
}
int mid = (left+right)/2;
if(j <= mid) return query(2*pos, left, mid, i, j);
else if(i >= mid + 1) return query(2*pos+1, mid + 1, right, i, j);
else return query(2*pos, left, mid, i, j) * query(2*pos+1, mid + 1, right, i, j);
}
int main(){
scanf("%d %d", &N, &Q);
for(int i = 1; i <= N; i++){
scanf("%d", &arr[i]);
}
build(1, 1, N);
for(int q = 1; q <= Q; q++){
int op, l, r;
scanf("%d %d %d", &op, &l, &r);
if(op == 1){
arr[l] = r;
update(1, 1, N, l);
}
else{
node result = query(1, 1, N, l, r);
printf("%lld\n", result.tot);
}
}
return 0;
}
Compilation message
garaza.cpp: In member function 'node node::operator*(const node&) const':
garaza.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < other.pref.size(); i++){
~~^~~~~~~~~~~~~~~~~~~
garaza.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < suf.size(); i++){
~~^~~~~~~~~~~~
garaza.cpp:89:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < other.pref.size() && gcd(suf[i].first, other.pref[j].first) > 1){
~~^~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
garaza.cpp:192:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
garaza.cpp:200:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &op, &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
17016 KB |
Output is correct |
| 2 |
Correct |
33 ms |
17272 KB |
Output is correct |
| 3 |
Correct |
45 ms |
17528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
20344 KB |
Output is correct |
| 2 |
Correct |
220 ms |
21956 KB |
Output is correct |
| 3 |
Correct |
251 ms |
21468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
386 ms |
25092 KB |
Output is correct |
| 2 |
Correct |
521 ms |
25564 KB |
Output is correct |
| 3 |
Correct |
545 ms |
26360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
930 ms |
34040 KB |
Output is correct |
| 2 |
Correct |
991 ms |
34048 KB |
Output is correct |
| 3 |
Correct |
1016 ms |
32632 KB |
Output is correct |
