Submission #598139

#TimeUsernameProblemLanguageResultExecution timeMemory
598139nguyen31hoang08minh2003Sirni (COCI17_sirni)C++14
42 / 140
963 ms158540 KiB
/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= \==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\ \\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ /==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\ =/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\= //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= \==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\ \\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ /==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\ =/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\= //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= */ #include <bits/stdc++.h> #define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i) #define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i) #define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i) #define fi first #define se second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef unsigned long long ull; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; /* min(x % y, y % x) = max(x, y) % min(x, y) */ const int maxN = 1e5 + 5, maxK = 1e7 + 7, inf = 0x3f3f3f3f, ninf = 0xc0c0c0c0; class SegmentTree { private: int n; vi it; void update(int ql, int qr, int val, int i, int l, int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { maxi(it[i], val); return; } const int m = l + r >> 1; update(ql, qr, val, i << 1, l, m); update(ql, qr, val, i << 1 | 1, m + 1, r); } int query(int q, int i, int l, int r) const { if (q < l || r < q) return ninf; if (l == r) return it[i]; const int m = l + r >> 1; return max({it[i], query(q, i << 1, l, m), query(q, i << 1 | 1, m + 1, r)}); } public: SegmentTree() {}; SegmentTree(const int n): n(n), it(n + 5 << 2, ninf) {}; void update(int ql, int qr, int val) { update(ql, qr, val, 1, 1, n); } int query(int q) const { return q - query(q, 1, 1, n); } }; int n, p[maxN]; vi k; void input() { cin >> n; k.resize(n); fort(i, 1, n) { cin >> p[i]; k[i - 1] = i; } } void subtask1() { // Prim algorithm const int N = n + 5; int x; ll res = 0; vi d(N, inf); vector<bool> vis(N); d[1] = 0; fort(_, 1, n) { x = -1; fort(i, 1, n) { if (vis[i]) continue; if (x < 0 || d[x] > d[i]) x = i; } vis[x] = true; res += d[x]; fort(i, 1, n) { if (vis[i]) continue; mini(d[i], min(p[x] % p[i], p[i] % p[x])); } } cout << res << '\n'; } void subtask3() { ll res = 0; SegmentTree it(maxK); sort(all(k), [&](const int &x, const int &y) -> bool { return p[x] < p[y]; }); const int maxp = p[k.back()]; it.update(p[k[0]], p[k[0]], p[k[0]]); for (const int &i : k) { res += it.query(p[i]); for (int j = 0; j <= maxp; j += p[i]) it.update(j, min(j + p[i] - 1, maxp), j); } cout << res << '\n'; } int main() { #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); input(); if (n <= 7500) subtask1(); else subtask3(); return 0; }

Compilation message (stderr)

sirni.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
sirni.cpp:76:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         const int m = l + r >> 1;
      |                       ~~^~~
sirni.cpp: In member function 'int SegmentTree::query(int, int, int, int) const':
sirni.cpp:86:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         const int m = l + r >> 1;
      |                       ~~^~~
sirni.cpp: In constructor 'SegmentTree::SegmentTree(int)':
sirni.cpp:92:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   92 |     SegmentTree(const int n): n(n), it(n + 5 << 2, ninf) {};
      |                                        ~~^~~
#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...
#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...