| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 170311 |
2019-12-24T19:02:17 Z |
ryansee |
Garaža (COCI17_garaza) |
C++14 |
|
1521 ms |
34168 KB |
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T,typename B> inline T gcd(T a,B b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<int,int>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
int n, q;
struct stuff { vector<pi>pre,suf; ll v=0; };
struct node {
stuff v;
node *l,*r;
node(int s,int e) { int m=(s+e)>>1;
// s=_S,e=_E,m=(s+e)>>1;
v.pre.clear(),v.suf.clear();
if(s^e) {
l=new node(s,m);
r=new node(m+1,e);
}
}
// typedef pair<deque<pi>,deque<pi>> dqpi;
void update(int s,int e,int x,int nval) {
if(s==e) {
v.pre.clear(), v.suf.clear(), v.pre.eb(nval,s), v.suf.eb(nval,s), v.v=nval!=1;
return;
}
int m=(s+e)>>1;
if(x>m) r->update(m+1,e,x,nval);
else l->update(s,m,x,nval);
if(l->v.pre.size()&&r->v.pre.size()) v = merge(l->v,r->v,s,e,m);
// v.s=s,v.e=e,v.m=m;
}
stuff merge(stuff l,stuff r,int lds,int rde,int m,bool dg=0) {
// if(dg) cerr<<"start: "<<l.s<<' '<<l.e<<' '<<r.e<<'\n';
stuff v;
// if(l.pre.empty() || r.pre.empty()) return v;
if(dg) cerr<<l.v<<' '<<r.v<<'\n';
v.v=l.v+r.v;
l.suf.insert(l.suf.begin(), pi(1, lds-1));
int ls=0;
FOR(i,1,siz(l.suf)-1) {
ll stop = rde+1;
ll now = l.suf[i].f;
if(now != 1) {
// for(auto j:r.pre) {
// if(gcd(j.f,now)==1) { stop=j.s; break; }
// now=gcd(now,j.f);
// }
FOR(j,ls,r.pre.size()-1) {
now=gcd(r.pre[j].f,now);
if(now==1) { stop=r.pre[j].s; break; }
ls=j+1;
}
} else {
stop = m+1;
}
v.v += (l.suf[i].s-l.suf[i-1].s) * (stop-(m+1));
}
if(dg) cerr<<v.v-l.v-r.v<<'\n'<<'\n';
l.suf.erase(l.suf.begin());
v.pre=l.pre;
ll now=v.pre.back().f;
if(now != 1) {
for(auto i:r.pre) {
// if(gcd(i.f,now)==1) { v.pre.eb(1, i.s); break; }
// ll on=now;
// now=gcd(i.f,now);
// if(on^now) v.pre.eb(now, i.s);
if(i.f%now) now=gcd(now,i.f), v.pre.eb(now,i.s);
}
}
v.suf=r.suf;
now=v.suf[0].f;
if(now != 1) {
reverse(all(l.suf));
for(auto i:l.suf) {
// if(gcd(i.f,now)==1) { v.suf.emplace_front(1, i.s); break; }
// ll on = now;
// now=gcd(i.f,now);
// if(on^now) v.suf.emplace_front(now,i.s);
if(i.f%now) now=gcd(now,i.f), v.suf.insert(v.suf.begin(), {now,i.s});
}
reverse(all(l.suf));
}
if(dg) {
for(auto i:v.pre) cerr<<i.f<<' '<<i.s<<'\n';
cerr<<"\n";
for(auto i:v.suf) cerr<<i.f<<' '<<i.s<<'\n';
cerr<<"\n";
for(auto i:l.suf) cerr<<i.f<<' '<<i.s<<'\n';
cerr<<'\n';
}
return v;
}
stuff rmq(int s,int e,int x,int y) {
if(s==x&&e==y) {
return v;
}
int m=(s+e)>>1;
if(x>m) return r->rmq(m+1,e,x,y);
else if(y<=m) return l->rmq(s,m,x,y);
else return merge(l->rmq(s,m,x,m),r->rmq(m+1,e,m+1,y),x,y,m);
}
} *seg;
int main()
{
FAST
cin>>n>>q;
seg=new node(1,n);
FOR(i,1,n) { ll a; cin>>a; seg->update(1,n,i,a); }
// stuff tmp = seg->rmq(1,n);
// cerr<<"\n\n";
// cerr<<tmp.v<<'\n';
// for(auto i:tmp.pre) cerr<<i.f<<' '<<i.s<<'\n';
// cerr<<'\n';
// for(auto i:tmp.suf) cerr<<i.f<<' '<<i.s<<'\n';
// return 0;
FOR(ii,1,q) {
ll op; cin>>op;
if(op==1) {
ll x, v; cin>>x>>v;
seg->update(1,n,x,v);
} else {
ll l, r; cin>>l>>r;
cout<<seg->rmq(1,n,l,r).v<<'\n';
}
}
return 0;
}
/*
4 1
2 2 2 2
2 1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
632 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
46 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
240 ms |
7108 KB |
Output is correct |
| 2 |
Correct |
333 ms |
10012 KB |
Output is correct |
| 3 |
Correct |
401 ms |
10028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
717 ms |
16556 KB |
Output is correct |
| 2 |
Correct |
794 ms |
17468 KB |
Output is correct |
| 3 |
Correct |
863 ms |
19192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1357 ms |
33004 KB |
Output is correct |
| 2 |
Correct |
1478 ms |
34168 KB |
Output is correct |
| 3 |
Correct |
1521 ms |
31884 KB |
Output is correct |
