| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257463 |
2020-08-04T09:48:29 Z |
NONAME |
Garaža (COCI17_garaza) |
C++14 |
|
2041 ms |
34828 KB |
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;
const int N = int(1e5) + 500;
int n, q;
int a[N];
struct tree {
tree *L, *R;
vector <pair <int, int> > pf, sf;
ll cnt;
tree() {
L = R = 0;
cnt = 0;
pf.clear(); sf.clear();
}
void merge(tree *Left, tree *Right) {
vector <pair <int, int> > lft, rgt;
(this -> pf).clear();
(this -> sf).clear();
lft = (Left -> pf);
rgt = (Right -> pf);
for (int i = 0; i < int(lft.size()); ++i)
(this -> pf).push_back(lft[i]);
for (int i = 0; i < int(rgt.size()); ++i) {
int gcd = __gcd(rgt[i].first, (this -> pf).back().first);
if (gcd == (this -> pf).back().first) (this -> pf).back().second += rgt[i].second;
else (this -> pf).push_back(make_pair(gcd, rgt[i].second));
}
lft = (Left -> sf);
rgt = (Right -> sf);
for (int i = 0; i < int(rgt.size()); ++i)
(this -> sf).push_back(rgt[i]);
for (int i = 0; i < int(lft.size()); ++i) {
int gcd = __gcd(lft[i].first, (this -> sf).back().first);
if (gcd == (this -> sf).back().first) (this -> sf).back().second += lft[i].second;
else (this -> sf).push_back(make_pair(gcd, lft[i].second));
}
(this -> cnt) = (Left -> cnt) + (Right -> cnt);
lft = (Left -> sf);
rgt = (Right -> pf);
vector <int> pref(int(rgt.size()), 0);
pref.clear();
for (int i = 0; i < int(rgt.size()); ++i)
pref[i] = (i - 1 < 0 ? 0 : pref[i - 1]) + rgt[i].second;
int p = int(rgt.size()) - 1;
for (int i = 0; i < int(lft.size()); ++i) {
while (p >= 0 && __gcd(lft[i].first, rgt[p].first) == 1)
--p;
if (p < 0)
break;
(this -> cnt) += lft[i].second * 1ll * pref[p];
}
}
void build(int tl, int tr) {
if (tl > tr)
return;
if (tl == tr) {
cnt = (a[tl] != 1);
pf.push_back(make_pair(a[tl], 1));
sf.push_back(make_pair(a[tl], 1));
return;
}
int md = (tl + tr) >> 1;
L = new tree();
R = new tree();
L -> build(tl, md);
R -> build(md + 1, tr);
merge(L, R);
}
void update(int tl, int tr, int p, int vl) {
if (tl == tr) {
a[tl] = vl;
cnt = (a[tl] != 1);
pf[0] = sf[0] = make_pair(a[tl], 1);
return;
}
int md = (tl + tr) >> 1;
if (p <= md) L -> update(tl, md, p, vl);
else R -> update(md + 1, tr, p, vl);
merge(L, R);
}
pair <ll, pair <vector <pair <int, int> >, vector <pair <int, int> > > > query(int tl, int tr, int ql, int qr) {
vector <pair <int, int> > npf, nsf;
npf.clear(); nsf.clear();
if ((tl > tr) || (ql > tr) || (tl > qr))
return make_pair(0ll, make_pair(npf, nsf));
if ((tl >= ql) && (tr <= qr))
return make_pair(cnt, make_pair(pf, sf));
int md = (tl + tr) >> 1;
auto res1 = L -> query(tl, md, ql, qr);
auto res2 = R -> query(md + 1, tr, ql, qr);
ll cur_res = 0;
vector <pair <int, int> > lft, rgt;
lft = res1.second.first;
rgt = res2.second.first;
for (int i = 0; i < int(lft.size()); ++i)
npf.push_back(lft[i]);
for (int i = 0; i < int(rgt.size()); ++i) {
if (npf.empty()) {
npf.push_back(rgt[i]);
continue;
}
int gcd = __gcd(rgt[i].first, npf.back().first);
if (gcd == npf.back().first) npf.back().second += rgt[i].second;
else npf.push_back(make_pair(gcd, rgt[i].second));
}
lft = res1.second.second;
rgt = res2.second.second;
for (int i = 0; i < int(rgt.size()); ++i)
nsf.push_back(rgt[i]);
for (int i = 0; i < int(lft.size()); ++i) {
if (nsf.empty()) {
nsf.push_back(lft[i]);
continue;
}
int gcd = __gcd(lft[i].first, nsf.back().first);
if (gcd == nsf.back().first) nsf.back().second += lft[i].second;
else nsf.push_back(make_pair(gcd, lft[i].second));
}
cur_res = res1.first + res2.first;
lft = res1.second.second;
rgt = res2.second.first;
vector <int> pref(int(rgt.size()), 0);
pref.clear();
for (int i = 0; i < int(rgt.size()); ++i)
pref[i] = (i - 1 < 0 ? 0 : pref[i - 1]) + rgt[i].second;
int p = int(rgt.size()) - 1;
for (int i = 0; i < int(lft.size()); ++i) {
while (p >= 0 && __gcd(lft[i].first, rgt[p].first) == 1)
--p;
if (p < 0)
break;
cur_res += lft[i].second * 1ll * pref[p];
}
return make_pair(cur_res, make_pair(npf, nsf));
}
//void show(int tl, int tr) {
//cerr << tl + 1 << " " << tr + 1 << " " << cnt << "\n";
//for (auto i : pf)
//cerr << i.first << " " << i.second << "\n";
//cerr << "---------\n";
//for (auto i : sf)
//cerr << i.first << " " << i.second << "\n";
//cerr << "\n";
//}
//void result(int tl, int tr) {
//if (tl > tr)
//return;
//if (tl == tr) {
//show(tl, tr);
//return;
//}
//int md = (tl + tr) >> 1;
//L -> result(tl, md);
//R -> result(md + 1, tr);
//show(tl, tr);
//}
} t;
int main() {
fast_io;
cin >> n >> q;
for (int i = 0; i < n; ++i)
cin >> a[i];
t.build(0, n - 1);
//t.result(0, n - 1);
//cerr << "!!!!!\n";
while (q--) {
int type;
cin >> type;
if (type == 1) {
int x, y;
cin >> x >> y;
--x;
t.update(0, n - 1, x, y);
//t.result(0, n - 1);
//cerr << "!!!!!!\n";
} else {
int x, y;
cin >> x >> y;
--x, --y;
cout << (t.query(0, n - 1, x, y)).first << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
640 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
52 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
7288 KB |
Output is correct |
| 2 |
Correct |
569 ms |
10360 KB |
Output is correct |
| 3 |
Correct |
352 ms |
10104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
759 ms |
17256 KB |
Output is correct |
| 2 |
Correct |
1210 ms |
17520 KB |
Output is correct |
| 3 |
Correct |
790 ms |
20088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2041 ms |
33936 KB |
Output is correct |
| 2 |
Correct |
1698 ms |
34828 KB |
Output is correct |
| 3 |
Correct |
1376 ms |
33392 KB |
Output is correct |
