| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55738 |
2018-07-08T18:21:22 Z |
hamzqq9 |
Garaža (COCI17_garaza) |
C++14 |
|
1286 ms |
43292 KB |
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1000000001
#define N 100005
#define LOG 20
#define magic 100
#define MAX 1000005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) 1ll*((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
int flag=0;
struct SEG {
int bas,son;
ll result;
int szpre,szsuf;
vector<ii> pre,suf;
} S[N*4];
int n,q,t,x,y,a[N];
SEG merge(SEG A,SEG B) {
SEG res;
res.bas=A.bas;
res.son=B.son;
res.result=A.result+B.result;
int last=-1;
int now=sz(A.suf)-1;
int totszB=0;
while(now+1) {
ii suf_el=A.suf[now];
now--;
while(last+1<sz(B.pre) && __gcd(suf_el.st,B.pre[last+1].st)>1) totszB+=B.pre[last+1].nd,last++;
res.result+=1ll*suf_el.nd*totszB;
}
if(A.szpre==A.son-A.bas+1) {
int last=-1;
while(last+1<sz(B.pre) && __gcd(A.pre.back().st,B.pre[last+1].st)>1) {
int tut=__gcd(A.pre.back().st,B.pre[last+1].st);
last++;
if(tut==A.pre.back().st) {
A.pre.back().nd+=B.pre[last].nd;
}
else {
A.pre.pb({tut,B.pre[last].nd});
}
}
}
if(B.szsuf==B.son-B.bas+1) {
int last=-1;
while(last+1<sz(A.suf) && __gcd(B.suf.back().st,A.suf[last+1].st)>1) {
int tut=__gcd(B.suf.back().st,A.suf[last+1].st);
last++;
if(tut==B.suf.back().st) {
B.suf.back().nd+=A.suf[last].nd;
}
else {
B.suf.pb({tut,A.suf[last].nd});
}
}
}
res.pre=A.pre;
res.suf=B.suf;
res.szpre=res.szsuf=0;
for(auto x:res.pre) res.szpre+=x.nd;
for(auto x:res.suf) res.szsuf+=x.nd;
return res;
}
SEG get(int node,int bas,int son,int x,int y) {
if(bas>=x && son<=y) return S[node];
if(orta>=x) {
if(orta+1<=y) {
return merge(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y));
}
else {
return get(node*2,bas,orta,x,y);
}
}
else return get(node*2+1,orta+1,son,x,y);
}
void up(int node,int bas,int son,int x,int val) {
if(bas>x || son<x) return ;
if(bas==x && son==x) {
S[node].pre.clear();
S[node].suf.clear();
S[node].result=S[node].szpre=S[node].szsuf=0;
if(val>1) {
S[node].szpre=S[node].szsuf=S[node].result=1;
S[node].pre.pb({val,1});
S[node].suf.pb({val,1});
}
return ;
}
up(node*2,bas,orta,x,val);
up(node*2+1,orta+1,son,x,val);
S[node]=merge(S[node*2],S[node*2+1]);
}
void build(int node,int bas,int son) {
if(bas==son) {
S[node].bas=bas;
S[node].son=son;
if(a[bas]>1) {
S[node].pre.pb({a[bas],1});
S[node].suf.pb({a[bas],1});
S[node].szpre=S[node].szsuf=S[node].result=1;
}
return ;
}
build(node*2,bas,orta);
build(node*2+1,orta+1,son);
S[node]=merge(S[node*2],S[node*2+1]);
}
int main() {
#if 0
freopen("input.txt","r",stdin);
#endif
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
build(1,1,n);
while(q--) {
scanf("%d %d %d",&t,&x,&y);
if(t==1) {
up(1,1,n,x,y);
}
else {
SEG res=get(1,1,n,x,y);
printf("%lld\n",res.result);
}
}
}
Compilation message
garaza.cpp: In function 'int main()':
garaza.cpp:229: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:233:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
garaza.cpp:241:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&t,&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
28536 KB |
Output is correct |
| 2 |
Correct |
50 ms |
29028 KB |
Output is correct |
| 3 |
Correct |
68 ms |
29296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
31432 KB |
Output is correct |
| 2 |
Correct |
354 ms |
33160 KB |
Output is correct |
| 3 |
Correct |
431 ms |
33160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
35844 KB |
Output is correct |
| 2 |
Correct |
653 ms |
35916 KB |
Output is correct |
| 3 |
Correct |
799 ms |
36908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1276 ms |
43292 KB |
Output is correct |
| 2 |
Correct |
1286 ms |
43292 KB |
Output is correct |
| 3 |
Correct |
1221 ms |
43292 KB |
Output is correct |
