제출 #659062

#제출 시각아이디문제언어결과실행 시간메모리
659062Danilo21게임 (IOI13_game)C++14
37 / 100
13095 ms87044 KiB
#include <bits/stdc++.h> #include "game.h" #define ll long long #define ld long double #define pb push_back #define fi first #define se second #define en '\n' #define sp ' ' #define tb '\t' #define ri(n) int n; cin >> n #define rl(n) ll n; cin >> n #define rs(s) string s; cin >> s #define rc(c) char c; cin >> c #define rv(v) for (auto &x : v) cin >> x #define pven(v) for (auto x : v) cout << x << en #define pv(v) for (auto x : v) cout << x << sp; cout << en #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define yes cout << "YES" << en #define no cout << "NO" << en #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) #define ssort(a, b) if (a < b) swap(a, b) #define bitcnt(a) (__builtin_popcountll(a)) #define bithigh(a) (63-__builtin_clzll(a)) #define lg bithigh #define highpow(a) (1LL << (ll)lg(a)) using namespace std; long long gcd2(long long X, long long Y) { long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } struct node{ ll x; node(ll v = 0){ update(v); } node update(ll v, vector<ll> params = {}){ x = v; return *this; } static node op(const node& a, const node& b){ return node(gcd2(a.x, b.x)); } }; template<class T> class segtree{ int n; vector<T> tree; T update(int s, int l, int r, int pos, vector<ll> params){ if (pos < l || pos > r) return tree[s]; if (l == r){ ll x = params[0]; params = vector<ll>(params.begin()+1, params.end()); tree[s].update(x, params); return tree[s]; } int m = (l + r)>>1; T a = update(2*s, l, m, pos, params); T b = update(2*s+1, m+1, r, pos, params); return tree[s] = T::op(a, b); } T query(int s, int l, int r, int ql, int qr) const { if (l > qr || r < ql) return T(); if (l >= ql && r <= qr) return tree[s]; int m = (l + r)>>1; T a = query(2*s, l, m, ql, qr); T b = query(2*s+1, m+1, r, ql, qr); return T::op(a, b); } public: segtree<T>(int n = 0, const T& a = T()){ Assign(n, a); } void Assign(int s, const T& a){ n = highpow(s); if (bitcnt(s) > 1) n <<= 1; tree.assign(2*n, a); } static segtree<T> op(const segtree<T>& a, const segtree<T>& b){ int n = max(a.n, b.n); segtree<T> r(n); for (int i = 1; i < 2*n; i++) r.tree[i] = T::op((a.n ? a.tree[i] : T()), (b.n ? b.tree[i] : T())); return r; } T update(int pos, vector<ll> params){ return update(1, 0, n-1, pos, params); } T query(int l, int r) const { return query(1, 0, n-1, l, r); } }; const ll LINF = 4e18; const int mxN = 1e3+10, INF = 2e9; ll n, m, a[mxN]; segtree<segtree<node> > st; void init(int R, int C){ st.Assign(C, segtree<node>(R)); } void update(int P, int Q, long long K) { st.update(Q, {P, K}); } long long calculate(int P, int Q, int U, int V) { auto tree = st.query(Q, V); return tree.query(P, U).x; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...