# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248343 |
2020-07-12T09:19:39 Z |
VEGAnn |
Sirni (COCI17_sirni) |
C++14 |
|
2864 ms |
786436 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define i3 array<int,3>
using namespace std;
typedef long long ll;
const int N = 100100;
const int BIG = int(1e7) + 10;
const int cn = int(1e4);
const int oo = 2e9;
bool del[BIG];
vector<i3> edg;
vector<int> vc, elms[N], nwv;
int mrk[BIG], n, nt[BIG];
ll ans = 0;
int get(int x) { return (x == nt[x] ? x : nt[x] = get(nt[x])); }
void calc(){
for (int i = BIG - 2; i > 0; i--)
if (mrk[i])
nt[i] = i;
else nt[i] = nt[i + 1];
for (int cr : vc){
int cm = mrk[cr];
for (int x : elms[cm])
nt[get(x)] = get(x + 1);
for (int x : elms[cm]){
for (int i = get(x); i < BIG - 1; ){
int nw = i % x;
edg.PB({nw, i, x});
if (nw == 0)
i += x;
else i += x - nw;
i = get(i);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int i = 1; i <= n; i++){
int x; cin >> x;
mrk[x] = i;
}
int siz = 0;
for (int i = 1; i < BIG; i++)
if (mrk[i]) {
siz++;
vc.PB(i);
elms[mrk[i]].PB(i);
}
nt[BIG - 1] = BIG - 1;
calc();
reverse(all(vc));
calc();
sort(all(edg));
for (int cr : vc)
nt[cr] = cr;
for (i3 nw : edg){
int x = get(nw[1]), y = get(nw[0]);
if (x == y) continue;
ans += nw[0];
nt[x] = y;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1064 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
109 ms |
42132 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1410 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
370 ms |
61920 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
145 ms |
49588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
716 ms |
98864 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
194 ms |
50212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2864 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2208 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1143 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |