| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 720822 |
2023-04-09T11:39:38 Z |
cpptowin |
Garaža (COCI17_garaza) |
C++14 |
|
117 ms |
262144 KB |
#include<bits/stdc++.h>
#define db double
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 5010
#define fi first
#define se second
#define pb push_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000000
#define pii pair<int,int>
#define vii vector<pii>
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(j<<1))
#define vi vector<int>
#define vvi vector<vector<int>>
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int M = 1 << 24;
int m, n, t, k, a[N], ans, b[N], c[N], d[N];
int dp[N], tong;
vector<int> zero;
struct node
{
vector<pii> L, R;
int val;
node()
{
L.clear();
R.clear();
val = 0;
}
};
struct IT
{
int n;
vector<node> st;
IT(int _n): n(_n),st(4*_n+5){};
node add(node x, node y, int l, int r)
{
node res;
res.val=x.val+y.val;
int v=x.L.back().fi;
res.L=x.L;
for (auto u : y.L)
{
v = __gcd(v,u.fi);
if (v==res.L.back().fi)continue;
res.L.pb({v,u.se});
}
v=y.R.back().fi;
res.R=y.R;
for (pii u : x.R)
{
v=__gcd(v, u.fi);
if(v==res.R.back().fi)continue;
res.R.pb({v,u.se});
}
if (__gcd(x.R[0].fi, y.L[0].fi)==1) return res;
int j=0;
while (j+1<y.L.size()&& __gcd(x.R[0].fi, y.L[j + 1].fi)>1) ++j;
for (int i=0;i<x.R.size(); i++)
{
while (j>=0&& __gcd(x.R[i].fi, y.L[j].fi)==1) --j;
if (j<0) break;
res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
}
return res;
}
void build(int id, int l, int r)
{
if (l==r)
{
st[id].L.pb({a[l],l});
st[id].R.pb({a[l],l});
st[id].val =(a[l]> 1);
return;
}
int mid=(l+r)>> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
st[id]=add(st[id<<1],st[id<<1|1],l,r);
}
void update(int id,int l,int r,int pos)
{
if (l==r)
{
st[id].L[0].fi = a[l];
st[id].R[0].fi = a[l];
st[id].val =(a[l]>1);
return;
}
int mid=(l+r)>>1;
if (pos <= mid) update(id << 1, l, mid, pos);
else update(id << 1 | 1, mid + 1, r, pos);
st[id] = add(st[id << 1], st[id << 1 | 1], l, r);
}
node get(int id, int l, int r, int u, int v)
{
if (u <= l && r <= v) return st[id];
int mid = (l + r) >> 1;
if (v <= mid) return get(id << 1, l, mid, u, v);
if (mid + 1 <= u) return get(id << 1 | 1, mid + 1, r, u, v);
return add(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v), max(l, u), min(r, v));
}
};
void process()
{
cin >> n >> m;
fo(i,1,n) cin >> a[i];
IT tree(n);
tree.build(1,1,n);
while (m--)
{
int l, r;
cin >> t >> l >> r;
if (t == 1)
{
a[l] = r;
tree.update(1,1,n,l);
}
else cout << tree.get(1,1,n,l, r).val << '\n';
}
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
process();
}
Compilation message
garaza.cpp: In member function 'node IT::add(node, node, long long int, long long int)':
garaza.cpp:82:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while (j+1<y.L.size()&& __gcd(x.R[0].fi, y.L[j + 1].fi)>1) ++j;
| ~~~^~~~~~~~~~~
garaza.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i=0;i<x.R.size(); i++)
| ~^~~~~~~~~~~
garaza.cpp:87:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
| ~^~~~~~~~~~~~~~
garaza.cpp:87:78: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
| ~^~~~~~~~~~~~~~
garaza.cpp: At global scope:
garaza.cpp:146:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
146 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1676 KB |
Output is correct |
| 3 |
Correct |
39 ms |
2484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
