| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 849261 |
2023-09-14T10:16:38 Z |
nnhzzz |
Garaža (COCI17_garaza) |
C++14 |
|
850 ms |
44832 KB |
// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define int ll
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 1e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
struct T{
vpii l,r;
int res;
T(){
l.clear(); r.clear(); res = 0;
}
T(int x){
l.clear(); r.clear();
l.emplace_back(x,1);
r.emplace_back(x,1);
res = x!=1;
}
};
T merge(T a,T b){
T ans = T();
for(auto &[i,ci]:a.r){
for(auto &[j,cj]:b.l){
if(__gcd(i,j)!=1){
ans.res += 1LL*ci*cj;
}
}
}
ans.res += a.res+b.res;
ans.l.insert(ans.l.begin(),ALL(a.l));
for(auto &[j,cj]:b.l){
int g = __gcd(ans.l.back().fi,j);
if(g==ans.l.back().fi){
ans.l.back().se += cj;
}else{
ans.l.emplace_back(g,cj);
}
}
//-----------------------------------
ans.r.insert(ans.r.begin(),ALL(b.r));
for(auto &[j,cj]:a.r){
int g = __gcd(ans.r.back().fi,j);
if(g==ans.r.back().fi){
ans.r.back().se += cj;
}else{
ans.r.emplace_back(g,cj);
}
}
return ans;
}
T st[MAXN<<2];
int a[MAXN];
void build(int id, int l, int r){
if(l==r){
st[id] = T(a[l]);
return ;
}
int mid = (l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
st[id] = merge(st[id<<1],st[id<<1|1]);
}
void update(int id, int l, int r, int pos, int val){
if(l==r){
st[id] = T(val);
return ;
}
int mid = (l+r)>>1;
if(pos<=mid) update(id<<1,l,mid,pos,val);
else update(id<<1|1,mid+1,r,pos,val);
st[id] = merge(st[id<<1],st[id<<1|1]);
}
T get(int id, int l, int r, int lo, int hi){
if(l>=lo && r<=hi){
return st[id];
}
int mid = (l+r)>>1;
if(hi<=mid) return get(id<<1,l,mid,lo,hi);
if(lo>mid) return get(id<<1|1,mid+1,r,lo,hi);
T res = merge(get(id<<1,l,mid,lo,hi),get(id<<1|1,mid+1,r,lo,hi));
return res;
}
void solve(){
int n,q; cin >> n >> q;
REP(i,1,n){
cin >> a[i];
}
build(1,1,n);
while(q--){
int t,l,r; cin >> t >> l >> r;
if(t==1){
update(1,1,n,l,r);
}else{
cout << get(1,1,n,l,r).res << "\n";
}
}
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message
garaza.cpp: In function 'T merge(T, T)':
garaza.cpp:59:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | for(auto &[i,ci]:a.r){
| ^
garaza.cpp:60:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for(auto &[j,cj]:b.l){
| ^
garaza.cpp:68:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for(auto &[j,cj]:b.l){
| ^
garaza.cpp:78:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | for(auto &[j,cj]:a.r){
| ^
garaza.cpp: In function 'int main()':
garaza.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
23132 KB |
Output is correct |
| 2 |
Correct |
19 ms |
23644 KB |
Output is correct |
| 3 |
Correct |
32 ms |
24404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
27476 KB |
Output is correct |
| 2 |
Correct |
190 ms |
29268 KB |
Output is correct |
| 3 |
Correct |
151 ms |
28752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
33648 KB |
Output is correct |
| 2 |
Correct |
433 ms |
34056 KB |
Output is correct |
| 3 |
Correct |
353 ms |
34824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
779 ms |
44724 KB |
Output is correct |
| 2 |
Correct |
850 ms |
44832 KB |
Output is correct |
| 3 |
Correct |
663 ms |
42804 KB |
Output is correct |
