| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 80378 |
2018-10-20T12:23:37 Z |
mbvdk |
Garaža (COCI17_garaza) |
C++14 |
|
4000 ms |
76244 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 100000;
int a[N+5];
struct node{
vector<pii> l, r;
ll ans;
};
node st[4*N+5];
node merge(node a, node b){
node res;
int g = 0, cnt = 0;
for(int i=0;i<a.l.size();i++){
g = __gcd(g, a.l[i].first);
cnt += a.l[i].second;
res.l.emplace_back(pii(g, cnt));
}
for(int i=0;i<b.l.size();i++){
g = __gcd(g, b.l[i].first);
cnt += b.l[i].second;
res.l.emplace_back(pii(g, cnt));
}
g = 0, cnt = 0;
for(int i=0;i<b.r.size();i++){
g = __gcd(g, b.r[i].first);
cnt += b.r[i].second;
res.r.emplace_back(pii(g, cnt));
}
for(int i=0;i<a.r.size();i++){
g = __gcd(g, a.r[i].first);
cnt += a.r[i].second;
res.r.emplace_back(pii(g, cnt));
}
res.ans = a.ans + b.ans;
int j = a.r.size()-1;
for(int i=0;i<b.l.size();i++){
while(j >= 0 && __gcd(b.l[i].first, a.r[j].first) == 1) j--;
if(j >= 0){
int ri = b.l[i].second;
int le = a.r[j].second;
if(i != 0) ri -= b.l[i-1].second;
res.ans += (ll)le*ri;
}
}
return res;
}
void build(int n, int s, int e){
if(s == e){
st[n].l.emplace_back(pii(a[s], 1));
st[n].r.emplace_back(pii(a[s], 1));
if(a[s] != 1) st[n].ans = 1;
}
else{
int mid = (s+e)/2;
build(n+n, s, mid);
build(n+n+1, mid+1, e);
st[n] = merge(st[n+n], st[n+n+1]);
}
}
void update(int n, int s, int e, int idx, int v){
if(s == e){
a[s] = v;
st[n].l.clear();
st[n].r.clear();
st[n].ans = 0;
st[n].l.emplace_back(pii(a[s], 1));
st[n].r.emplace_back(pii(a[s], 1));
if(a[s] != 1) st[n].ans = 1;
}
else{
int mid = (s+e)/2;
if(idx <= mid) update(n+n, s, mid, idx, v);
else update(n+n+1, mid+1, e, idx, v);
st[n] = merge(st[n+n], st[n+n+1]);
}
}
node query(int n, int s, int e, int l, int r){
if(s > r || l > e) return node();
if(l <= s && e <= r) return st[n];
int mid = (s+e)/2;
return merge(query(n+n, s, mid, l, r), query(n+n+1, mid+1, e, l, r));
}
int main(){
int n, q;
scanf("%d%d", &n, &q);
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
}
build(1, 1, n);
while(q--){
int t, l, r;
scanf("%d%d%d", &t, &l, &r);
if(t == 1){
update(1, 1, n, l, r);
}
else{
printf("%lld\n", query(1, 1, n, l, r).ans);
}
}
}
Compilation message
garaza.cpp: In function 'node merge(node, node)':
garaza.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.l.size();i++){
~^~~~~~~~~~~
garaza.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<b.l.size();i++){
~^~~~~~~~~~~
garaza.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<b.r.size();i++){
~^~~~~~~~~~~
garaza.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.r.size();i++){
~^~~~~~~~~~~
garaza.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<b.l.size();i++){
~^~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:95: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:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
garaza.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &t, &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
22648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4011 ms |
33980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
48540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4022 ms |
76244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
