結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2020-04-24 21:49:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,806 bytes |
コンパイル時間 | 3,462 ms |
コンパイル使用メモリ | 226,348 KB |
最終ジャッジ日時 | 2025-01-09 23:29:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 TLE * 6 |
ソースコード
#pragma region Macros#pragma GCC optimize("O3")#include <bits/stdc++.h>#define ll long long#define ld long double#define rep2(i,a,b) for(ll i=a;i<=b;++i)#define rep(i,n) for(ll i=0;i<n;i++)#define rep3(i,a,b) for(ll i=a;i>=b;i--)#define pii pair<int,int>#define pll pair<ll,ll>#define pq priority_queue#define pb push_back#define eb emplace_back#define vec vector<int>#define vecll vector<ll>#define vecpii vector<pii>#define vecpll vector<pll>#define vec2(a,b) vector<vec>(a,vec(b))#define vec2ll(a,b) vector<vecll>(a,vecll(b))#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))#define fi first#define se second#define all(c) begin(c),end(c)#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define lb(c,x) distance(c.begin(),lower_bound(all(c),(x)))#define ub(c,x) distance(c.begin(),upper_bound(all(c),(x)))using namespace std;int in() {int x;cin>>x;return x;}ll lin() {ll x;cin>>x;return x;}string stin() {string s;cin>>s;return s;}template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}vec iota(int n){vec a(n);iota(all(a),0);return a;}void print(){putchar(' ');}void print(bool a){cout<<a;}void print(int a){cout<<a;}void print(long long a){cout<<a;}void print(char a){cout<<a;}void print(string &a){cout<<a;}void print(double a){cout<<a;}template<class T> void print(const vector<T>&);template<class T, size_t size> void print(const array<T, size>&);template<class T, class L> void print(const pair<T, L>& p);template<class T, size_t size> void print(const T (&)[size]);template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i);} cout<<endl;}template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i);} }template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }template<class T, class L> void print(const pair<T, L>& p){ cout<<'(';print(p.first); cout<<","; print(p.second);cout<<')'; }template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ cout<<" "; print(*i); } }template<class T> void print(const T& a){ cout << a; }int out(){ putchar('\n'); return 0; }template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }vector<pll> factor(ll x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }vector<int> divisor(int x){ vector<int> ans; for(int i=1;i*i<=x;i++)if(x%i==0){ans.pb(i);if(i*i!=x)ans.pb(x/i);} return ans;}template<class T> void UNIQUE(vector<T> &x){sort(all(x));x.erase(unique(all(x)),x.end());}int popcount(ll x){return __builtin_popcountll(x);}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int rnd(int n){return uniform_int_distribution<int>(0, n)(rng);}#define _GLIBCXX_DEBU#define endl '\n'#ifdef _MY_DEBUG#undef endl#define debug(x) cout<<#x<<": "<<x<<endlvoid err(){}template<class T> void err(const T& t){ print(t); cout<<" ";}template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }#else#define debug(x)template<class... T> void err(const T&...){}#endif#pragma endregiontemplate< typename Monoid >struct SegmentTree {using F = function< Monoid(Monoid, Monoid) >;int sz;vector< Monoid > seg;const F f;const Monoid M1;SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x) {seg[k + sz] = x;}void build() {for(int k = sz - 1; k > 0; k--) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}void update(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid query(int a, int b) {Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const {return seg[k + sz];}template< typename C >int find_subtree(int a, const C &check, Monoid &M, bool type) {while(a < sz) {Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);if(check(nxt)) a = 2 * a + type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template< typename C >int find_first(int a, const C &check) {Monoid L = M1;if(a <= 0) {if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) {Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template< typename C >int find_last(int b, const C &check) {Monoid R = M1;if(b >= sz) {if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1) {if(b & 1) {Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};constexpr int N = 500010;// RSQSegmentTree<ll> seg(N,[](ll x,ll y){return gcd(x,y);},0);SegmentTree<ll> seg2(N,[](ll x,ll y){return min(x,y);},LONG_LONG_MAX);signed main(){ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);int n;cin>>n;vecll a;rep(i,n)seg.set(i,lin());vecll b;seg.build();rep(i,n){b.pb(seg.find_first(i,[](ll x){return x==1;}));if(b.back()==-1)b.back()=n;}rep(i,n)seg2.set(i,b[i]);seg2.build();ll ans = 0;rep(i,n){int l = i-1,r = n;while(l<r-1){int mid =(l+r)>>1;if(seg2.query(i,mid+1) <=mid) r = mid;else l = mid;}ans+=l-i+1;}cout << (ll)((ll)n*(n+1)/2)-ans<<endl;}