Submission #1082276

#TimeUsernameProblemLanguageResultExecution timeMemory
1082276steveonalexNadan (COCI18_nadan)C++17
50 / 50
1 ms460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() #define block_of_code if(true) ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(a, b);} ll lcm(ll a, ll b){return a / gcd(a, b) * b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ll mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} double rngesus_d(double l, double r){ double cur = rngesus(0, MASK(60) - 1); cur /= MASK(60) - 1; return l + cur * (r - l); } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } const int INF = 1e9 + 69; struct SegmentTreeMM{ int n; vector<pair<int, int>> a; SegmentTreeMM(int _n){ n = _n; a.resize(n * 2 + 2, {INF, -INF}); } pair<int, int> combine(pair<int, int> x, pair<int, int> y){ return make_pair(min(x.first, y.first), max(x.second, y.second)); } void update(int i, int v){ i += n; a[i] = {v, v}; while(i > 1){ i >>= 1; a[i] = combine(a[i * 2], a[i * 2 + 1]); } } pair<int, int> get(int l, int r){ l += n; r += n + 1; pair<int, int> ans = {INF, -INF}; while(l < r){ if (l & 1) ans = combine(ans, a[l++]); if (r & 1) ans = combine(ans, a[--r]); l >>= 1; r >>= 1; } return ans; } }; struct SegmentTreeGCD{ int n; vector<int> a; SegmentTreeGCD(int _n){ n = _n; a.resize(n * 2 + 2, 0); } void update(int i, int v){ i += n; a[i] = v; while(i > 1){ i >>= 1; a[i] = gcd(a[i * 2], a[i * 2 + 1]); } } int get(int l, int r){ l += n; r += n + 1; int ans = 0; while(l < r){ if (l & 1) ans = gcd(ans, a[l++]); if (r & 1) ans = gcd(ans, a[--r]); l >>= 1; r >>= 1; } return ans; } }; struct Counter{ map<int, int> mp; int ans; Counter(){ ans = 0; } void add(int x){ mp[x]++; ans += (mp[x] == 1); } void del(int x){ mp[x]--; ans -= (mp[x] == 0); } int get(){return ans;} }; ll solve(){ int n; cin >> n; vector<int> a(n+2); for(int i = 1; i<=n; ++i) cin >> a[i]; SegmentTreeMM st(n); for(int i = 1; i<=n; ++i) st.update(i, a[i]); SegmentTreeGCD st_gcd(n); for(int i = 1; i<n; ++i) st_gcd.update(i, abs(a[i] - a[i+1])); Counter accountant; vector<int> nxt(n+1, n+1); for(int i = n; i>=1; --i){ nxt[i] = nxt[i+1]; if (a[i] != a[i+1]) nxt[i] = i + 1; } ll ans = 0; int less_than_four = 1; int smol_gcd = 1; int big_distinct = 1; accountant.add(a[1]); for(int i = 1; i<=n; ++i){ maximize(less_than_four, i); maximize(smol_gcd, i); while(less_than_four <= n){ pair<int, int> cur = st.get(i, less_than_four); if (cur.second - cur.first < 3) less_than_four++; else break; } while(smol_gcd <= n){ int cur = st_gcd.get(i, smol_gcd - 1); if (cur == 0 || cur != LASTBIT(cur)) smol_gcd++; else break; } while(big_distinct <= n){ if (accountant.get() < 2){ big_distinct++; if (big_distinct <= n) accountant.add(a[big_distinct]); } else break; } ans += less_than_four - i; ll suffix = max(big_distinct, smol_gcd); maximize(suffix, less_than_four); ans += n + 1 - suffix; accountant.del(a[i]); } // for(int i = 1; i<=n; ++i) { // ll g = 0; // pair<int, int> cu = {INF, -INF}; // for(int j = i; j<=n; ++j){ // g = gcd(g, a[j]); // if (g == 1) break; // cu = SegmentTreeMM.combine(cu, {a[j], a[j]}); // ll cur = cu.second - cu.first; // if (cur == LASTBIT(cur)) ans++; // } // } return ans; } int main(void){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); clock_t start = clock(); int n, k; cin >> n >> k; for(int i = 1; i<k; ++i) { cout << i << "\n"; n -= i; } cout << n << "\n"; cerr << "Time elapsed: " << clock() - start << " ms\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...