| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 81189 |
2018-10-24T04:01:53 Z |
ngot23 |
Garaža (COCI17_garaza) |
C++11 |
|
1171 ms |
237556 KB |
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=100005;
int n, Q, a[N];
struct node {
int demP, demS, P[35], S[35], cntP[35], cntS[35];
long long res;
node() {
demP=demS=0;
res=0;
memset(P, 0, sizeof P);
memset(S, 0, sizeof S);
memset(cntP, 0, sizeof cntP);
memset(cntS, 0, sizeof cntS);
}
node (node &lef, node &rig) {
rep(i, 1, lef.demP) {
P[i]=lef.P[i];
cntP[i]=lef.cntP[i];
}
/// tinh prefix gcd
demP=lef.demP;
int id=1;
int gcd=lef.P[lef.demP];
for(; id<=rig.demP ; ++id) {
int xx=__gcd(gcd, rig.P[id]);
if(xx!=gcd) break;
cntP[demP]+=rig.cntP[id];
}
while(id<=rig.demP) {
P[++demP]=__gcd(gcd, rig.P[id]);
cntP[demP]=rig.cntP[id];
int id2=id+1;
for(; id2<=rig.demP ; ++id2) {
int xx=__gcd(gcd, rig.P[id2]);
if(xx!=P[demP]) break;
cntP[demP]+=rig.cntP[id2];
}
id=id2;
}
rep(i, 1, rig.demS) {
S[i]=rig.S[i];
cntS[i]=rig.cntS[i];
}
/// tinh suffix gcd
demS=rig.demS;
id=1;
gcd=rig.S[rig.demS];
for(; id<=lef.demS ; ++id) {
int xx=__gcd(gcd, lef.S[id]);
if(xx!=gcd) break;
cntS[demS]+=lef.cntS[id];
}
while(id<=lef.demS) {
S[++demS]=__gcd(gcd, lef.S[id]);
cntS[demS]=lef.cntS[id];
int id2=id+1;
for(; id2<=lef.demS ; ++id2) {
int xx=__gcd(gcd, lef.S[id2]);
if(xx!=S[demS]) break;
cntS[demS]+=lef.cntS[id2];
}
id=id2;
}
/// hop res 2 cay
res=lef.res+rig.res;
id=0;
int sum=0;
for(int i=lef.demS ; i ; --i) {
while(__gcd(lef.S[i], rig.P[id+1])!=1&&id<rig.demP) { ++id; sum+=rig.cntP[id]; }
res+=1ll*sum*lef.cntS[i];
}
}
};
node it[N*4];
void build(int l, int r, int id) {
if(l==r) {
it[id].demP=it[id].demS=it[id].cntP[1]=it[id].cntS[1]=1;
it[id].P[1]=it[id].S[1]=a[l];
if(a[l]!=1) it[id].res=1;
else it[id].res=0;
return;
}
int mid=(r+l)>>1;
build(l, mid, id*2);
build(mid+1, r, id*2+1);
it[id]=node(it[id*2], it[id*2+1]);
}
void update(int l, int r, int id, int x) {
if(l==r) {
it[id].demP=it[id].demS=it[id].cntP[1]=it[id].cntS[1]=1;
it[id].P[1]=it[id].S[1]=a[l];
if(a[l]!=1) it[id].res=1;
else it[id].res=0;
return;
}
int mid=(r+l)>>1;
if(x<=mid) update(l, mid, id*2, x);
else update(mid+1, r, id*2+1, x);
it[id]=node(it[id*2], it[id*2+1]);
}
node get(int l, int r, int id, int u, int v) {
if(r<u||v<l) return node();
if(u<=l&&r<=v) return it[id];
int mid=(r+l)>>1;
node m1=get(l, mid, id*2, u, v);
node m2=get(mid+1, r, id*2+1, u, v);
return node(m1, m2);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(Task".inp", "r", stdin);
//freopen(Task".out", "w", stdout);
cin >> n >> Q;
rep(i, 1, n) cin >> a[i];
build(1, n, 1);
while(Q--) {
int t, x, y;
cin >> t >> x >> y;
if(t==1) {
a[x]=y;
update(1, n, 1, x);
} else {
cout << get(1, n, 1, x, y).res << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
225784 KB |
Output is correct |
| 2 |
Correct |
187 ms |
226036 KB |
Output is correct |
| 3 |
Correct |
199 ms |
226296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
320 ms |
226336 KB |
Output is correct |
| 2 |
Correct |
426 ms |
227204 KB |
Output is correct |
| 3 |
Correct |
425 ms |
227780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
582 ms |
228076 KB |
Output is correct |
| 2 |
Correct |
742 ms |
229744 KB |
Output is correct |
| 3 |
Correct |
738 ms |
231092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1114 ms |
233196 KB |
Output is correct |
| 2 |
Correct |
1146 ms |
235084 KB |
Output is correct |
| 3 |
Correct |
1171 ms |
237556 KB |
Output is correct |
